제출 #1007558

#제출 시각아이디문제언어결과실행 시간메모리
1007558c2zi6코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
6164 ms20688 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "elephants.h" const int BUCKETSIZE = 400; const int DBUCKETSIZE = 2*BUCKETSIZE + 2; int l; int m = 0; int st[DBUCKETSIZE]; struct BUCKET { int n = 0; int b[DBUCKETSIZE]; int cnt[DBUCKETSIZE]; int mx[DBUCKETSIZE]; void rem(int x) { while (b[n-1] > x) { st[m++] = b[--n]; } --n; while (m) { b[n++] = st[--m]; } } void add(int x) { while (n && b[n-1] > x) { st[m++] = b[--n]; } b[n++] = x; while (m) { b[n++] = st[--m]; } } void recalc() { if (n >= 2*BUCKETSIZE + 2) cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA KOD KARMIR KOD KARMIR AAAAAAAAAAAAAAAAAAAAAAAA" << endl; reprl(i, n-1, 0) { int j = upper_bound(b, b+n, b[i] + l) - b; if (j == n) { cnt[i] = 1; mx[i] = b[i]+l; } else { cnt[i] = cnt[j]+1; mx[i] = mx[j]; } } } void print() { rep(i, n) cout << b[i] << " "; cout << endl; /*rep(i, n) cout << cnt[i] << " "; cout << endl;*/ /*rep(i, n) cout << mx[i] << " "; cout << endl;*/ } }; int n; int a[160000]; int b[160000]; vector<BUCKET> buk; void recalc() { rep(i, n) b[i] = a[i]; sort(b, b+n); buk.clear(); buk.pb(BUCKET()); rep(i, n) { if (buk.back().n >= BUCKETSIZE) { buk.pb(BUCKET()); } buk.back().add(b[i]); } for (BUCKET& p : buk) p.recalc(); } void add(int x) { for (BUCKET& p : buk) if (p.n) { if (x <= p.b[p.n-1]) { p.add(x); p.recalc(); return; } } buk.back().add(x); buk.back().recalc(); } void rem(int x) { for (BUCKET& p : buk) if (p.n) { if (x <= p.b[p.n-1]) { p.rem(x); p.recalc(); return; } } } int answer() { int ans = 0; int R = -2e9; for (BUCKET& p : buk) if (p.n) { int i = upper_bound(p.b, p.b + p.n, R) - p.b; if (i == p.n) continue; ans += p.cnt[i]; R = p.mx[i]; } return ans; } void print() { rep(i, n) cout << a[i] << " "; cout << endl; for (BUCKET& p : buk) { cout << "BUCKET: " << endl << " "; p.print(); } cout << "END OF PHASE ----------------------------------------------" << endl; } void init(int N, int L, int X[]) { n = N; l = L; rep(i, n) a[i] = X[i]; recalc(); } int qr = 0; int update(int i, int y) { if (qr++ % BUCKETSIZE == 0) { recalc(); /*cout << "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_RECALCULATED_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" << endl;*/ } rem(a[i]); a[i] = y; add(a[i]); /*print();*/ return answer(); }

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

elephants.cpp: In member function 'void BUCKET::print()':
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:77:9: note: in expansion of macro 'rep'
   77 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:77:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |                                        ^~~~
elephants.cpp: In function 'void print()':
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, n) cout << a[i] << " "; cout << endl;
      |     ^~~
elephants.cpp:134:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  134 |     rep(i, n) cout << a[i] << " "; cout << endl;
      |                                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...