Submission #18035

#	Time	Username	Problem	Language	Result	Execution time	Memory
18035		ainta	여왕벌 (KOI15_queen)	C++98	101 / 100	3050 ms	56548 KiB

Main

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int n, Q, Sx[710][710], Sy[710][710];
char p[710][710][28];
struct A{
    int a, b, c;
    A operator +(const A &x){
        A t;
        t.a = a+x.a, t.b = b+x.b, t.c = c+x.c;
        return t;
    }
    A operator -(const A &x){
        A t;
        t.a = a-x.a, t.b = b-x.b, t.c = c-x.c;
        return t;
    }
};
A Start(A x, int num){
    A t;
    t.a = min(x.a, num);
    t.b = min(x.b, num - t.a);
    t.c = min(x.c, num - t.a - t.b);
    return t;
}
A End(A x, int num){
    A t;
    t.c = min(x.c, num);
    t.b = min(x.b, num - t.c);
    t.a = min(x.a, num - t.c - t.b);
    return t;
}
int Num(A x){
    int cnt = x.a + x.b + x.c;
    return x.a * (cnt+cnt+3-x.a) / 2 + x.b;
}
void Addx(int x, int by, int ey, A tp, int c){
    Sx[x][by + tp.a]+=c;
    Sx[x][by + tp.a + tp.b]+=c;
    Sx[x][by + tp.a + tp.b + tp.c]-= c*2;
}
void Addy(int y, int bx, int ex, A tp, int c){
    Sy[bx][y]+=2*c;
    Sy[bx + tp.c][y]-=c;
    Sy[bx + tp.c + tp.b][y]-= c;
}
void Add(A *tp, int k, int ck){
    if(k == 0)tp->a += ck;
    else if(k == 1)tp->b += ck;
    else tp->c += ck;
}
void Do(int bx, int by, int ex, int ey, vector<A> &ret, vector<int>C){
    int i, j, k, cnt = ex-bx+ey-by+1, mx, my, cnt2, sz, pv;
    A tp, tp2, tp3, tp4, tp5, tres;
    ret.resize((cnt+1)*(cnt+2)/2);
    if(bx == ex){
        for(i=0;i<=cnt;i++){
            for(j=0;j<=cnt - i;j++){
                k = cnt-i-j;
                tp.a=i,tp.b=j,tp.c=k;
                ret[Num(tp)] = tp;
            }
        }
        return;
    }
    if(by == ey){
        for(i=0;i<=cnt;i++){
            for(j=0;j<=cnt - i;j++){
                k = cnt-i-j;
                tp.a=i,tp.b=j,tp.c=k;
                ret[Num(tp)] = tp;
            }
        }
        return;
    }
    if(bx + 1 == ex && by + 1 == ey){
        int t, tw[3], l, pv = 0;
        for(i=0;i<=3;i++){
            for(j=0;j<=3-i;j++){
                k = 3-i-j;
                tp.a=i,tp.b=j,tp.c=k;
                tp2 = tp;
                for(l=0;l<i;l++)tw[l]=0;
                for(l=i;l<i+j;l++)tw[l]=1;
                for(l=i+j;l<3;l++)tw[l]=2;
                Add(&tp2, tw[1], -1);
                t = p[ex][ey][tw[0]*9+tw[1]*3+tw[2]];
                if(t == 'L')Add(&tp2, tw[0], 1);
                if(t == 'D')Add(&tp2, tw[1], 1);
                if(t == 'U')Add(&tp2, tw[2], 1);
                ret[Num(tp)] = tp2;
                Addx(ex, ey, ey, tp2 - Start(tp2, 1) - End(tp2, 1), C[pv]);
                pv++;
            }
        }
        return;
    }
    mx = (bx + ex + 1)>>1, my = (by + ey + 1)>>1;
    vector<int>CNT;
    vector<A>res, res2, res3, res4;
    cnt2 = mx-bx+my-by+1;
    sz = (cnt2+1)*(cnt2+2)/2;
    CNT.resize(sz);
    res.resize(sz);
    res2.resize(sz);
    res3.resize(sz);
    res4.resize(sz);
    pv = 0;
    for(i=0;i<=cnt;i++){
        for(j=0;j<=cnt-i;j++){
            k = cnt - i -j;
            tp.a = i,tp.b = j, tp.c =k;
            tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
            CNT[Num(tp2)]+=C[pv];
            pv++;
        }
    }
 
 
 
    Do(bx,by,mx,my, res, CNT);
 
    for(i=0;i<sz;i++)CNT[i]=0;
    pv = 0;
    for(i=0;i<=cnt;i++){
        for(j=0;j<=cnt-i;j++){
            k = cnt - i -j;
            tp.a = i,tp.b = j, tp.c =k;
            tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
            tp = Start(tp, ex-mx) + Start(res[Num(tp2)], my - by + 1);
            CNT[Num(tp)] += C[pv];
            pv++;
        }
    }
 
    Do(mx,by,ex,my,res2, CNT);
 
    for(i=0;i<sz;i++)CNT[i]=0;
    pv = 0;
    for(i=0;i<=cnt;i++){
        for(j=0;j<=cnt-i;j++){
            k = cnt - i - j;
            tp.a = i,tp.b = j, tp.c = k;
            tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
            tp = End(res[Num(tp2)], mx - bx + 1) + End(tp, ey-my);
            CNT[Num(tp)] += C[pv];
            pv++;
        }
    }
    Do(bx,my,mx,ey,res3, CNT);
 
 
 
    for(i=0;i<sz;i++)CNT[i]=0;
    pv = 0;
    for(i=0;i<=cnt;i++){
        for(j=0;j<=cnt-i;j++){
            k = cnt - i - j;
            tp.a = i,tp.b = j, tp.c = k;
            tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
            tp3 = Start(tp, ex-mx) + Start(res[Num(tp2)], my - by + 1);
            tp4 = End(res[Num(tp2)], mx - bx + 1) + End(tp, ey-my);
            tp = End(res2[Num(tp3)], ex - mx + 1) + Start(res3[Num(tp4)], ey - my + 1) - Start(res3[Num(tp4)], 1);
            CNT[Num(tp)] += C[pv];
            pv++;
        }
    }
    Do(mx,my,ex,ey,res4, CNT);
 
    pv = 0;
    for(i=0;i<=cnt;i++){
        for(j=0;j<=cnt-i;j++){
            k = cnt - i - j;
            tp.a = i,tp.b = j, tp.c = k;
            tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
            tp3 = Start(tp, ex-mx) + Start(res[Num(tp2)], my - by + 1);
            tp4 = End(res[Num(tp2)], mx - bx + 1) + End(tp, ey-my);
            tp5 = End(res2[Num(tp3)], ex - mx + 1) + Start(res3[Num(tp4)], ey - my + 1) - Start(res3[Num(tp4)], 1);
            tres = Start(res2[Num(tp3)], my - by) + res4[Num(tp5)] + End(res3[Num(tp4)], mx - bx);
            ret[Num(tp)] = tres;
            pv++;
        }
    }
}
int main(){
    int i, j, a, b, c;
    scanf("%d%d",&n,&Q);
    for(i=2;i<=n;i++){
        for(j=2;j<=n;j++){
            scanf("%s",p[i][j]);
        }
    }
    A tp;
    vector<A> ret;
    vector<int> C;
    C.resize((n+n)*(n+n+1)/2);
    while(Q--){
        scanf("%d%d%d",&a,&b,&c);
        tp.a = a, tp.b = b, tp.c = c;
        C[Num(tp)]++;
        Addy(1, 1, n, Start(tp, n), 1);
        Addx(1, 2, n, End(tp, n-1), 1);
    }
    Do(1, 1, n, n, ret, C);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)Sx[i][j]+=Sx[i][j-1];
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)Sy[i][j]+=Sy[i-1][j];
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            printf("%d ",Sx[i][j]+Sy[i][j]+1);
        }
        printf("\n");
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32
• Subtask 5: 1 / 1