oj.uz

Submission #74606

# Submission time Handle Problem Language Result Execution time Memory
74606 2018-09-05T05:27:01 Z cubecube1000 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1643 ms 239848 KB 
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef unsigned long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int MAX=(1<<20)+5;
const ll INFLL=0x3f3f3f3f3f3f3f;
bool dist[2][MAX];
int seg[2][MAX],cum[2][MAX],n,q;
int mp[MAX];
ll ans;
void update(int t1,int t2,int val){
    //printf("%d %d %d\n",t1,t2,val);
    if(t2<=0||t2>=(1<<n)) return;
    int v=t2&(-t2);
    if(val){if(seg[t1][t2]++==0) cum[t1][v]++, ans+=(ll)((1<<(n-mp[v]-1))-cum[!t1][v]);}
    else{if(--seg[t1][t2]==0) cum[t1][v]--, ans-=(ll)((1<<(n-mp[v]-1))-cum[!t1][v]);}
    update(t1,(t2^v)|(v<<1),val);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++) mp[1<<i]=i;
    for(int i=0;i<q;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        dist[t1][t2]=!dist[t1][t2],dist[t1][t2-1]=!dist[t1][t2-1];
        update(t1,t2,dist[t1][t2]); update(t1,t2-1,dist[t1][t2-1]);
        printf("%lld\n",ans*4ll+1ll);
    }
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:23: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:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t1,&t2);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 388 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 624 KB Output is correct
2 Correct 3 ms 652 KB Output is correct
3 Correct 3 ms 664 KB Output is correct
4 Correct 4 ms 692 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 4 ms 764 KB Output is correct
8 Correct 3 ms 788 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1632 ms 55580 KB Output is correct
2 Correct 1631 ms 72984 KB Output is correct
3 Correct 1370 ms 82584 KB Output is correct
4 Correct 1611 ms 106648 KB Output is correct
5 Correct 1570 ms 122548 KB Output is correct
6 Correct 1580 ms 138140 KB Output is correct
7 Correct 1580 ms 155456 KB Output is correct
8 Correct 1643 ms 171496 KB Output is correct
9 Correct 1354 ms 178044 KB Output is correct
10 Correct 1458 ms 194988 KB Output is correct
11 Correct 1517 ms 215312 KB Output is correct
12 Correct 1564 ms 230328 KB Output is correct
13 Correct 1370 ms 239848 KB Output is correct