2019牛客暑期多校训练营（第三场）

#include <bits/stdc++.h>
using namespace std;

const int N=100101;
int n,pre[N],num0,num1,a[N*3],ans;
char c[N];
int main(){
    scanf("%d",&n);
    scanf("%s",c);
    for (int i=0;i<n;i++){
        if (c[i]=='0'){
            num0++;
            pre[i]=pre[i-1]+1;
            if (a[pre[i]+N]==0){
                a[pre[i]+N]=i;
            }else{
                ans=max(ans,i-a[pre[i]+N]);
            }
        }
        if (c[i]=='1'){
            num1++;
            pre[i]=pre[i-1]-1;
            if (a[pre[i]+N]==0){
                a[pre[i]+N]=i;
            }else{
                ans=max(ans,i-a[pre[i]+N]);
            }
        }
        if (pre[i]==0){
            ans=max(ans,i+1);
        }
    }
    printf("%d %d
",ans,2*min(num0,num1));
}

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
int mx[maxn],mi[maxn],a[maxn][maxn];
int n,m,q[maxn][2];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                mx[j] = 0;
                mi[j] = inf;
            }
            for (int j = i; j <= n; j++) {
                int t1 = 0, t2 = 0, l = 1, l2 = 1, l1 = 1;
                for (int k = 1; k <= n; k++) {
                    mx[k] = max(mx[k], a[j][k]);
                    mi[k] = min(mi[k], a[j][k]);
                    while (t1 >= l1 && mx[q[t1][0]] <= mx[k]) t1--;
                    while (t2 >= l2 && mi[q[t2][1]] >= mi[k]) t2--;
                    q[++t1][0] = k;
                    q[++t2][1] = k;
                    while (k >= l && mx[q[l1][0]] - mi[q[l2][1]] > m) {
                        l++;
                        if (q[l1][0] < l) {
                            l1++;
                        }
                        if (q[l2][1] < l) {
                            l2++;
                        }
                    }
                    ans = max(ans, (k - l + 1) * (j - i + 1));
                }
            }
        }
        printf("%d
", ans);
    }
}

/*


// manacher ，后缎自动机，回文自 动机，字符串hash

//==========================
//manacher 求最长回文子串
//==========================
const int maxn=110010;
char ma[maxn*2];
int mp[maxn*2];
void manacher(char s[],int len) {
    int l = 0;
    ma[l++] = '$';
    ma[l++] = '#';
    for (int i = 0; i < len; i++) {
        ma[l++] = s[i];
        ma[l++] = '#';
    }
    ma[l] = 0;
    int mx = 0, id = 0;
    for (int i = 0; i < l; i++) {
        mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
        while (ma[i + mp[i]] == ma[i - mp[i]]) {
            mp[i]++;
        }
        if (i + mp[i] > mx) {
            mx = i + mp[i];
            id = i;
        }
    }
}

char s[maxn];
int main(){
    while (~scanf("%s",s)){
        int len=strlen(s);
        manacher(s,len);
        int ans=0;
        for (int i=0;i<len*2+2;i++){
            ans=max(ans,mp[i]-1)
        }
        printf("%d
",ans);
    }
}

//=======================
// AC自动机 HDU2222
// 求目标串中出现了几个模式串
//=======================

struct Trie{
    int next[maxn][26],fail[maxn],end[maxn];
    int root,l;
    int newnode(){
        for (int i=0;i<26;i++){
            next[i]=-1;
        }
        end[l++]=0;
        return l-1;
    }
    void init(){
        l=0;
        root=newnode();
    }
    void insert(char buf[]){
        int len=strlen(buf);
        int now=root;
        for (int i=0;i<len;i++){
            if (next[now][buf[i]-'a']==-1){
                next[now][buf[i]-'a']=newnode();
            }
            now=next[now][buf[i]-'a'];
        }
        end[now]++;
    }
    void build(){
        queue<int>Q;
    }

};


*/








#include<bits/stdc++.h>
using namespace std;
const int N=100000;
struct node{
    int x,y;
    bool operator<(const node &b)const {
        if (x==b.x){
            return y>b.y;
        }else{
            return x<b.x;
        }
    }
}a[N];
int n;
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i].x, &a[i].y);
        }
        sort(a + 1, a + n + 1);
        int ans1x = a[n / 2].x + 1;
        int ans2x = a[n / 2 + 1].x - 1;
        int ans1y = a[n / 2].y + 999000000;
        int ans2y = a[n / 2 + 1].y - 999000000;
        printf("%d %d %d %d
", ans1x, ans1y, ans2x, ans2y);


    }
}

#include<bits/stdc++.h>

using namespace std;
const int N=3e5+10;
long long ans;
int t,n,a[N];
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        ans=0;
        for (int i=1; i<=n; i++)
        {
            int l=i,r=i;
            long long sum=0;
            while (l>1&&sum+a[l-1]<a[i])
            {
                l--;
                sum+=a[l];

            }
            while (r<n&&sum+a[r+1]<a[i])
            {
                r++;
                sum+=a[r];

            }
            ans+=r-i+1;
            for (int j=l; j<i; j++)
            {
                sum-=a[j];
                while (r<n&&sum+a[r+1]<a[i])
                {
                    r++;
                    sum+=a[r];
                }
                ans+=r-i+1;
            }
        }
        printf("%lld
",(long long)n*(n+1)/2-ans);
    }
}