제출 #414907

#제출 시각아이디문제언어결과실행 시간메모리
414907Pro_ktmr즐거운 사진 수집 (JOI13_collecting)C++17
30 / 100
5093 ms42612 KiB
#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); } }

컴파일 시 표준 에러 (stderr) 메시지

collecting.cpp: In function 'int main()':
collecting.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:58:5: note: in expansion of macro 'rep'
   58 |     rep(i, 2) st[i].init(1<<N, [](int a, int b){ return a+b; }, 0);
      |     ^~~
collecting.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:64:5: note: in expansion of macro 'rep'
   64 |     rep(i, 2) cnt[i][N] = 1;
      |     ^~~
collecting.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:66:2: note: in expansion of macro 'rep'
   66 |  rep(i, Q){
      |  ^~~
collecting.cpp:74:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   74 |         while(r-l <= (1<<N) && st[T].query(l, r) == 0 || st[T].query(l, r) == r-l){
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
collecting.cpp:85:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |         while(r-l <= (1<<N) && st[T].query(l, r) == 0 || st[T].query(l, r) == r-l){
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
collecting.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
collecting.cpp:93:9: note: in expansion of macro 'rep'
   93 |         rep(i, N+1){
      |         ^~~
collecting.cpp:94:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   94 |             ans += cnt[0][i]*(1<<N-i);
      |                                  ~^~
collecting.cpp:95:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |             ans += cnt[1][i]*(1<<N-i);
      |                                  ~^~
collecting.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
collecting.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d%d", &T, &X);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...