Submission #22285

#	Time	Username	Problem	Language	Result	Execution time	Memory
22285		↓우리보다잘하는팀 (#40)	Donut-shaped Enclosure (KRIII5_DE)	C++98	7 / 7	1159 ms	33148 KiB

DE

#include<cstdio>
#include<algorithm>
#define SZ 1048576
using namespace std;
int n, L, R;
struct Seg{
    int x, y1, y2, s;
    bool operator <(const Seg &p)const{
        return x<p.x;
    }
}w[801000];
int Y[801000], Res;
struct Tree{
    int Mx, K;
}IT[SZ+SZ];
int cnt;
void Add(int nd, int x){
    IT[nd].Mx += x;
    IT[nd].K += x;
}
void Spread(int nd){
    Add(nd+nd, IT[nd].K);
    Add(nd+nd+1, IT[nd].K);
    IT[nd].K = 0;
}
void Ins(int nd, int b, int e, int s, int l, int x){
    if(b==s&&e==l){
        Add(nd, x);
        return;
    }
    Spread(nd);
    int m = (b+e)>>1;
    if(s<=m)Ins(nd+nd, b, m, s, min(m,l),x);
    if(l>m)Ins(nd+nd+1, m+1, e, max(m+1,s), l,x);
    IT[nd].Mx = max(IT[nd+nd].Mx, IT[nd+nd+1].Mx);
}
int main(){
    scanf("%d%d%d",&n,&L,&R);
    int i, x, y, c;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        w[cnt++] = {x-R,y-R,y+R,c};
        w[cnt++] = {x-L+1,y-R,y+R,-c};
        
        w[cnt++] = {x-L+1,y-R,y-L,c};
        w[cnt++] = {x+L,y-R,y-L,-c};
        
        w[cnt++] = {x-L+1,y+L,y+R,c};
        w[cnt++] = {x+L,y+L,y+R,-c};
        
        w[cnt++] = {x+L,y-R,y+R,c};
        w[cnt++] = {x+R+1,y-R,y+R,-c};
    }
    for(i=0;i<cnt;i+=2){
        Y[i]=w[i].y1;
        Y[i^1]=w[i].y2;
    }
    sort(Y,Y+cnt);
    for(i=0;i<cnt;i++){
        w[i].y1 = lower_bound(Y, Y+cnt, w[i].y1) - Y + 1;
        w[i].y2 = lower_bound(Y, Y+cnt, w[i].y2) - Y + 1;
    }
    sort(w,w+cnt);
    for(i=0;i<cnt;i++){
        Ins(1, 1, SZ, w[i].y1, w[i].y2, w[i].s);
        if(w[i].x!=w[i+1].x){
            Res = max(Res, IT[1].Mx);
        }
    }
    printf("%d\n",Res);
}

Compilation message (stderr)

DE.cpp: In function 'int main()':
DE.cpp:42:34: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-R,y-R,y+R,c};
                                  ^
DE.cpp:42:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-R,y-R,y+R,c};
                  ^
DE.cpp:43:37: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-L+1,y-R,y+R,-c};
                                     ^
DE.cpp:43:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-L+1,y-R,y+R,-c};
                  ^
DE.cpp:45:36: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-L+1,y-R,y-L,c};
                                    ^
DE.cpp:45:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-L+1,y-R,y-L,c};
                  ^
DE.cpp:46:35: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+L,y-R,y-L,-c};
                                   ^
DE.cpp:46:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+L,y-R,y-L,-c};
                  ^
DE.cpp:48:36: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-L+1,y+L,y+R,c};
                                    ^
DE.cpp:48:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x-L+1,y+L,y+R,c};
                  ^
DE.cpp:49:35: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+L,y+L,y+R,-c};
                                   ^
DE.cpp:49:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+L,y+L,y+R,-c};
                  ^
DE.cpp:51:34: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+L,y-R,y+R,c};
                                  ^
DE.cpp:51:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+L,y-R,y+R,c};
                  ^
DE.cpp:52:37: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+R+1,y-R,y+R,-c};
                                     ^
DE.cpp:52:18: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         w[cnt++] = {x+R+1,y-R,y+R,-c};
                  ^
DE.cpp:38:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&L,&R);
                             ^
DE.cpp:41:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x,&y,&c);
                                 ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5