oj.uz

Submission #216327

# Submission time Handle Problem Language Result Execution time Memory
216327 2020-03-27T06:09:14 Z rkm0959 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1646 ms 64208 KB 
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long double ldb;
typedef long long int ll;
typedef unsigned long long int ull;
typedef complex<double> base;

ll tot, cc, n, q;
ll cntA[21], cntB[21];
bool ONA[(1<<20)+300], ONB[(1<<20)+300];
int lg[(1<<20)+300], treeA[(1<<22)+400], treeB[(1<<22)+400];

void update_A(int index, int s, int e, int loc, bool v)
{
    if(s>loc || e<loc) return;
    if(s==loc && e==loc)
    {
        treeA[index]=v;
        return;
    }
    int m=(s+e)>>1;
    if(treeA[index]==0 || treeA[index]==e-s+1) cntA[lg[e-s+1]]--;
    update_A(index<<1, s, m, loc, v);
    update_A(index<<1|1, m+1, e, loc, v);
    treeA[index]=treeA[index<<1]+treeA[index<<1|1];
    if(treeA[index]==0 || treeA[index]==e-s+1) cntA[lg[e-s+1]]++;
}

void update_B(int index, int s, int e, int loc, int v)
{
    if(s>loc || e<loc) return;
    if(s==loc && e==loc)
    {
        treeB[index]=v;
        return;
    }
    int m=(s+e)>>1;
    if(treeB[index]==0 || treeB[index]==e-s+1) cntB[lg[e-s+1]]--;
    update_B(index<<1, s, m, loc, v);
    update_B(index<<1|1, m+1, e, loc, v);
    treeB[index]=treeB[index<<1]+treeB[index<<1|1];
    if(treeB[index]==0 || treeB[index]==e-s+1) cntB[lg[e-s+1]]++;
}

int main(void)
{
    fio; cin>>n>>q; int i, whi, x;
    for(i=0 ; i<=n ; i++) cntA[i]=cntB[i]=(1<<(n-i));
    for(i=0 ; i<=n ; i++) lg[1<<i]=i;
    for(i=0 ; i<=n ; i++) tot+=cntA[i]*cntB[i];
    while(q--)
    {
        cin>>whi>>x; cc=0;
        if(whi==0) { ONA[x]^=1; update_A(1, 1, 1<<n, x, ONA[x]); }
        if(whi==1) { ONB[x]^=1; update_B(1, 1, 1<<n, x, ONB[x]); }
        for(i=1 ; i<=n ; i++) cc+=4LL*cntA[i]*cntB[i];
        cout<<tot-cc<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1646 ms 63916 KB Output is correct
2 Correct 1594 ms 63848 KB Output is correct
3 Correct 1351 ms 51836 KB Output is correct
4 Correct 1586 ms 64208 KB Output is correct
5 Correct 1596 ms 63612 KB Output is correct
6 Correct 1494 ms 62536 KB Output is correct
7 Correct 1584 ms 63864 KB Output is correct
8 Correct 1528 ms 63928 KB Output is correct
9 Correct 1330 ms 50424 KB Output is correct
10 Correct 1403 ms 53072 KB Output is correct
11 Correct 1507 ms 62456 KB Output is correct
12 Correct 1493 ms 62608 KB Output is correct
13 Correct 1331 ms 52856 KB Output is correct