oj.uz

Submission #414904

# Submission time Handle Problem Language Result Execution time Memory
414904 2021-05-31T10:33:03 Z Pro_ktmr 즐거운 사진 수집 (JOI13_collecting) C++17
30 / 100
 5000 ms 54528 KB 
#pragma GCC target ("avx")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

template<typename T>
struct SegmentTree{
private:
    int N;
    vector<T> node;
    function<T(T, T)> F;
    T DEFAULT;
public:
    void init(int n, function<T(T, T)> f, T def){
        F = f;
        DEFAULT = def;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, DEFAULT);
    }
    T& operator [](int a){
        return node[a+N-1];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return DEFAULT;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

int N, Q;
int depth[(1<<20)+1];
SegmentTree<int> st[2];
ll cnt[2][21] ={};

signed main(){
	scanf("%d%d", &N, &Q);
    rep(i, 2) st[i].init(1<<N, [](int a, int b){ return a+b; }, 0);
    for(int i=1; i<=N; i++){
        for(int j=0; j<=(1<<N); j+=(1<<i)){
            depth[j] = i;
        }
    }
    rep(i, 2) cnt[i][N] = 1;

	rep(i, Q){
        int T, X;
        scanf("%d%d", &T, &X);
        X--;

        int l = X;
        int r = X+1;
        int level = 0;
        while(r-l <= (1<<N) && st[T].query(l, r) == 0 || st[T].query(l, r) == r-l){
            if(level != 0) cnt[T][level-1] += 2;
            if(depth[l] < depth[r]) l = l-(r-l);
            else r = r+(r-l);
            level++;
        }

        st[T].update(X, st[T][X]^1);
        l = X;
        r = X+1;
        level = 0;
        while(r-l <= (1<<N) && st[T].query(l, r) == 0 || st[T].query(l, r) == r-l){
            if(level != 0) cnt[T][level-1] -= 2;
            if(depth[l] < depth[r]) l = l-(r-l);
            else r = r+(r-l);
            level++;
        }

        ll ans = 0;
        rep(i, N+1){
            ans += cnt[0][i]*(1<<N-i);
            ans += cnt[1][i]*(1<<N-i);
            ans -= cnt[0][i]*cnt[1][i];
        }
        printf("%lld\n", ans);
	}
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:62:5: note: in expansion of macro 'rep'
   62 |     rep(i, 2) st[i].init(1<<N, [](int a, int b){ return a+b; }, 0);
      |     ^~~
collecting.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:68:5: note: in expansion of macro 'rep'
   68 |     rep(i, 2) cnt[i][N] = 1;
      |     ^~~
collecting.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:70:2: note: in expansion of macro 'rep'
   70 |  rep(i, Q){
      |  ^~~
collecting.cpp:78:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |         while(r-l <= (1<<N) && st[T].query(l, r) == 0 || st[T].query(l, r) == r-l){
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
collecting.cpp:89:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   89 |         while(r-l <= (1<<N) && st[T].query(l, r) == 0 || st[T].query(l, r) == r-l){
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
collecting.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:97:9: note: in expansion of macro 'rep'
   97 |         rep(i, N+1){
      |         ^~~
collecting.cpp:98:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   98 |             ans += cnt[0][i]*(1<<N-i);
      |                                  ~^~
collecting.cpp:99:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   99 |             ans += cnt[1][i]*(1<<N-i);
      |                                  ~^~
collecting.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
collecting.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d%d", &T, &X);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Correct 4 ms 292 KB Output is correct
4 Correct 6 ms 356 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 54528 KB Time limit exceeded
2 Halted 0 ms 0 KB -