Submission #51560644

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct line{
    int l,r,flag;
};
vector<line>p[800005];
int x[800005],y[800005],xx[800005],yy[800005];
int totx,toty;vector<int>p1,p2;
struct node{
    int sum;int l,r,lazy;
    void add(int x){lazy+=x;}
}tree[4000005];
void push_up(int k){
    if(tree[k].lazy == 0)tree[k].sum = tree[k<<1].sum+tree[k<<1|1].sum;
    else tree[k].sum = p1[tree[k].r-1]-p1[tree[k].l-1];
}
void build(int l,int r,int k){
    tree[k].l = l,tree[k].r = r;
    if(l+1 == r){
       return;
    }build(l,l+r>>1,k<<1),build(l+r>>1,r,k<<1|1);
}void upd(int k,int l,int r,int add){
	int ll = tree[k].l,rr = tree[k].r;
	if(l>=rr or ll>=r)return ;
	if(l<=ll and rr<=r){
		tree[k].add(add);push_up(k);return;
	}upd(k<<1,l,r,add),upd(k<<1|1,l,r,add);
	push_up(k);
}vector<int>pos[200005];int N;
signed main(){
    cin >> N;
    for(int i = 1;i<=N;i++)pos[i].push_back(0);
    for(int i=1;i<=N;i++){
		int a;cin >> a;pos[a].push_back(i);
	}for(int i= 1;i<=N;i++)pos[i].push_back(N+1);
	for(int i= 1;i<=N;i++){
		for(int j =0;j+2<pos[i].size();j++){
			x[++n] = pos[i][j],y[n] = pos[i][j+1];
			xx[n] = pos[i][j+1],yy[n] = pos[i][j+2];
		}
	}//for(int i = 1;i<=n;i++)cout << x[i] << " " << y[i] << " " << xx[i] << " " << yy[i] << endl;
	for(int i = 1;i<=n;i++){
        p1.push_back(x[i]);
        p1.push_back(xx[i]);
        p2.push_back(y[i]);
        p2.push_back(yy[i]);
    }sort(p1.begin(),p1.end());sort(p2.begin(),p2.end());
    p1.erase(unique(p1.begin(),p1.end()),p1.end());
    p2.erase(unique(p2.begin(),p2.end()),p2.end());
    totx = p1.size(),toty = p2.size();
    for(int i = 1;i<=n;i++){
        x[i] = lower_bound(p1.begin(),p1.end(),x[i])-p1.begin()+1;
        xx[i] = lower_bound(p1.begin(),p1.end(),xx[i])-p1.begin()+1;
        y[i] = lower_bound(p2.begin(),p2.end(),y[i])-p2.begin()+1;
        yy[i] = lower_bound(p2.begin(),p2.end(),yy[i])-p2.begin()+1;
        line x1;x1.l = x[i],x1.r = xx[i];
        x1.flag = 1;p[y[i]].push_back(x1);
        x1.flag = -1;p[yy[i]].push_back(x1);
    }build(1,totx+1,1);int ans = 0;
    for(int i = 1;i<toty;i++){
        for(auto x:p[i]){
            upd(1,x.l,x.r,x.flag);
        }ans+=tree[1].sum*(p2[i]-p2[i-1]);//assert(tree[1].sum<=p1.back()-p1[0]);
    }cout<<ans <<endl;
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void build(long long int, long long int, long long int)’:
Main.cpp:23:15: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   23 |     }build(l,l+r>>1,k<<1),build(l+r>>1,r,k<<1|1);
      |              ~^~
Main.cpp:23:34: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   23 |     }build(l,l+r>>1,k<<1),build(l+r>>1,r,k<<1|1);
      |                                 ~^~
Main.cpp: In function ‘int main()’:
Main.cpp:39:33: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   39 |                 for(int j =0;j+2<pos[i].size();j++){
      |                              ~~~^~~~~~~~~~~~~~

Judge Result