oj.uz

Submission #133249

# Submission time Handle Problem Language Result Execution time Memory
133249 2019-07-20T09:58:51 Z dantoh000 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1536 ms 61944 KB 
#include <bits/stdc++.h>
using namespace std;
int n,q;
struct node{
    int h;
    vector<int> a;
    vector<int> ct;
    node(int _h){
        h = _h;
        a = vector<int>((1<<(n+1))+1,0);
        ct = vector<int>(n+1,0);
    }
    void up(int x){
        int cur = n-1;
        x += (1<<n)-1;
        a[x] ^= 1;
        x >>= 1;
        while (x){
            if (a[x] == 2) ct[cur]--;
            //printf("%d depends %d %d\n",x,a[x<<1],a[(x<<1)+1]);
            if (a[x<<1] == a[(x<<1) + 1]) a[x] = a[x<<1];
            else a[x] = 2;
            if (a[x] == 2) ct[cur]++;
            x >>= 1;
            cur--;
        }
    }
}*rx, *ry;
int main(){
    scanf("%d%d",&n,&q);
    rx = new node(n), ry = new node(n);
    for (int i = 0; i < q; i++){
        int a, b;
        scanf("%d%d",&a,&b);
        if (a == 0){
            rx->up(b);
        }
        else ry->up(b);
        long long ans = 0;
        for (int i = 0; i < n; i++){
            //printf("size %d %lld\n",i,-1ll*rx->ct[i]*ry->ct[i]+(1ll<<i)*(rx->ct[i]+ry->ct[i]));
            ans -= 1ll*rx->ct[i]*ry->ct[i]-(1ll<<i)*(rx->ct[i]+ry->ct[i]);
        }
        printf("%lld\n",(ans<<2) + 1);
    }
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
collecting.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1510 ms 61644 KB Output is correct
2 Correct 1477 ms 61704 KB Output is correct
3 Correct 1269 ms 50760 KB Output is correct
4 Correct 1411 ms 61944 KB Output is correct
5 Correct 1451 ms 61472 KB Output is correct
6 Correct 1458 ms 60436 KB Output is correct
7 Correct 1459 ms 61556 KB Output is correct
8 Correct 1462 ms 61468 KB Output is correct
9 Correct 1250 ms 49100 KB Output is correct
10 Correct 1333 ms 51688 KB Output is correct
11 Correct 1431 ms 60240 KB Output is correct
12 Correct 1536 ms 60412 KB Output is correct
13 Correct 1330 ms 51716 KB Output is correct