oj.uz

Submission #18035

# Submission time Handle Problem Language Result Execution time Memory
18035 2016-01-18T13:27:03 Z ainta 여왕벌 (KOI15_queen) C++
101 / 100
 3050 ms 56548 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19312 KB Output is correct
2 Correct 0 ms 19312 KB Output is correct
3 Correct 42 ms 20100 KB Output is correct
4 Correct 41 ms 20100 KB Output is correct
5 Correct 432 ms 26192 KB Output is correct
6 Correct 419 ms 26192 KB Output is correct
7 Correct 425 ms 26192 KB Output is correct
8 Correct 1130 ms 38316 KB Output is correct
9 Correct 1152 ms 38316 KB Output is correct
10 Correct 2577 ms 56548 KB Output is correct
11 Correct 2622 ms 56548 KB Output is correct
12 Correct 2585 ms 56548 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19312 KB Output is correct
2 Correct 427 ms 26192 KB Output is correct
3 Correct 789 ms 31552 KB Output is correct
4 Correct 2612 ms 56548 KB Output is correct
5 Correct 2590 ms 56548 KB Output is correct
6 Correct 2598 ms 56548 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19312 KB Output is correct
2 Correct 43 ms 20100 KB Output is correct
3 Correct 1136 ms 38316 KB Output is correct
4 Correct 2600 ms 56548 KB Output is correct
5 Correct 2627 ms 56548 KB Output is correct
6 Correct 2620 ms 56548 KB Output is correct
7 Correct 2588 ms 56548 KB Output is correct
8 Correct 2561 ms 56548 KB Output is correct
9 Correct 2569 ms 56548 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1484 ms 38316 KB Output is correct
2 Correct 1473 ms 38316 KB Output is correct
3 Correct 2919 ms 56548 KB Output is correct
4 Correct 2933 ms 56548 KB Output is correct
5 Correct 3030 ms 56548 KB Output is correct
6 Correct 3050 ms 56548 KB Output is correct
7 Correct 2916 ms 56548 KB Output is correct
8 Correct 2921 ms 56548 KB Output is correct
9 Correct 2870 ms 56548 KB Output is correct
10 Correct 2892 ms 56548 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19312 KB Output is correct
2 Correct 0 ms 19312 KB Output is correct
3 Correct 0 ms 19312 KB Output is correct
4 Correct 0 ms 19312 KB Output is correct
5 Correct 290 ms 19312 KB Output is correct
6 Correct 261 ms 19312 KB Output is correct
7 Correct 267 ms 19312 KB Output is correct
8 Correct 267 ms 19312 KB Output is correct
9 Correct 2869 ms 56416 KB Output is correct
10 Correct 2868 ms 56416 KB Output is correct
11 Correct 2901 ms 56416 KB Output is correct
12 Correct 2995 ms 56416 KB Output is correct
13 Correct 2917 ms 56416 KB Output is correct
14 Correct 2843 ms 56548 KB Output is correct
15 Correct 2881 ms 56548 KB Output is correct
16 Correct 2879 ms 56548 KB Output is correct
17 Correct 2941 ms 56548 KB Output is correct
18 Correct 2936 ms 56548 KB Output is correct