제출 #503182

#제출 시각아이디문제언어결과실행 시간메모리
503182cig32푸드 코트 (JOI21_foodcourt)C++17
89 / 100
1082 ms171140 KiB
#include "bits/stdc++.h" using namespace std; #define int long long const int MAXN = 2.5e5 + 10; const int MOD = 1e9 + 7; mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } int bm(int b, int p) { // bigmod if(p==0) return 1; int r = bm(b, p/2); if(p&1) return (((r*r) % MOD) * b) % MOD; return (r*r) % MOD; } int N, M, Q; struct segtree_beats { bool cmp(long long x, long long y) { return x > y; } int stok; const long long extr = 2e18; struct node { long long max1, max2, maxc; long long min1, min2, minc; long long lazy, sum; long long l, r; }; vector<node> a; void pushtag_max(int idx, long long val) { if(val >= a[idx].max1) return; a[idx].sum -= (a[idx].max1 - val) * a[idx].maxc; a[idx].max1 = val; if(a[idx].l == a[idx].r) { a[idx].min1 = val; } else { if(a[idx].min1 >= val) { a[idx].min1 = val; a[idx].min2 = extr; a[idx].minc = a[idx].r - a[idx].l + 1; } else if(a[idx].min2 > val && a[idx].min2 != extr) { a[idx].min2 = val; } } } void pushtag_min(int idx, long long val) { if(val <= a[idx].min1) return; a[idx].sum += (val - a[idx].min1) * a[idx].minc; a[idx].min1 = val; if(a[idx].l == a[idx].r) { a[idx].max1 = val; } else { if(a[idx].max1 <= val) { a[idx].max1 = val; a[idx].max2 = -extr; a[idx].maxc = a[idx].r - a[idx].l + 1; } else if(a[idx].max2 < val && a[idx].max2 != -extr) { a[idx].max2 = val; } } } void pushtag_add(int idx, long long val) { a[idx].max1 += val; if(a[idx].max2 != -extr) a[idx].max2 += val; a[idx].min1 += val; if(a[idx].min2 != extr) a[idx].min2 += val; a[idx].lazy += val; a[idx].sum += val * (a[idx].r - a[idx].l + 1); } void pushdown(int idx) { pushtag_add(2*idx+1, a[idx].lazy); pushtag_add(2*idx+2, a[idx].lazy); a[idx].lazy = 0; pushtag_max(2*idx+1, a[idx].max1); pushtag_max(2*idx+2, a[idx].max1); pushtag_min(2*idx+1, a[idx].min1); pushtag_min(2*idx+2, a[idx].min1); } void pushup(int idx) { long long max1, max2, maxc; long long min1, min2, minc; long long lazy, sum; long long l, r; a[idx].max1 = max(a[2*idx+1].max1, a[2*idx+2].max1); a[idx].max2 = (a[2*idx+1].max1 == a[2*idx+2].max1 ? max(a[2*idx+1].max2, a[2*idx+2].max2) : (a[2*idx+1].max1 < a[2*idx+2].max1 ? max(a[2*idx+1].max1, a[2*idx+2].max2) : max(a[2*idx+1].max2, a[2*idx+2].max1) )); a[idx].maxc = (a[2*idx+1].max1 == a[2*idx+2].max1 ? a[2*idx+1].maxc + a[2*idx+2].maxc : (a[2*idx+1].max1 < a[2*idx+2].max1 ? a[2*idx+2].maxc : a[2*idx+1].maxc) ); a[idx].min1 = min(a[2*idx+1].min1, a[2*idx+2].min1); a[idx].min2 = (a[2*idx+1].min1 == a[2*idx+2].min1 ? min(a[2*idx+1].min2, a[2*idx+2].min2) : (a[2*idx+1].min1 > a[2*idx+2].min1 ? min(a[2*idx+1].min1, a[2*idx+2].min2) : min(a[2*idx+1].min2, a[2*idx+2].min1) )); a[idx].minc = (a[2*idx+1].min1 == a[2*idx+2].min1 ? a[2*idx+1].minc + a[2*idx+2].minc : (a[2*idx+1].min1 > a[2*idx+2].min1 ? a[2*idx+2].minc : a[2*idx+1].minc) ); a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum; } void init1(int l, int r, int idx, long long val) { a[idx].l = l, a[idx].r = r; if(l == r) { a[idx].max1 = a[idx].min1 = val; a[idx].max2 = -extr; a[idx].min2 = extr; a[idx].maxc = a[idx].minc = 1; a[idx].lazy = 0; a[idx].sum = val; return; } int mid = (l+r) >> 1; init1(l, mid, 2*idx+1, val); init1(mid+1, r, 2*idx+2, val); pushup(idx); } void u1(int l, int r, int constl, int constr, int idx, long long v) { if(v >= a[idx].max1) return; if(l<=constl && constr<=r && v>a[idx].max2) { pushtag_max(idx, v); return; } pushdown(idx); int mid = (constl+constr) >> 1; if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, v); else if(constr < l || r < mid+1) u1(l, r, constl, mid, 2*idx+1, v); else { u1(l, r, constl, mid, 2*idx+1, v); u1(l, r, mid+1, constr, 2*idx+2, v); } pushup(idx); } void u2(int l, int r, int constl, int constr, int idx, long long v) { if(v <= a[idx].min1) return; if(l<=constl && constr<=r && v<a[idx].min2) { pushtag_min(idx, v); return; } pushdown(idx); int mid = (constl+constr) >> 1; if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, v); else if(constr < l || r < mid+1) u2(l, r, constl, mid, 2*idx+1, v); else { u2(l, r, constl, mid, 2*idx+1, v); u2(l, r, mid+1, constr, 2*idx+2, v); } pushup(idx); } void u3(int l, int r, int constl, int constr, int idx, long long v) { if(l <= constl && constr <= r) { pushtag_add(idx, v); return; } pushdown(idx); int mid = (constl+constr) >> 1; if(mid < l || r < constl) u3(l, r, mid+1, constr, 2*idx+2, v); else if(constr < l || r < mid+1) u3(l, r, constl, mid, 2*idx+1, v); else { u3(l, r, constl, mid, 2*idx+1, v); u3(l, r, mid+1, constr, 2*idx+2, v); } pushup(idx); } long long qu(int l, int r, int constl, int constr, int idx) { if(l <= constl && constr <= r) { return a[idx].sum; } pushdown(idx); int mid = (constl+constr) >> 1; if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2); else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1); else { return qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2); } } public: void resize(int k) { stok = k; a.resize(4*k + 10); } void init(long long v) { // Initialize everything to v init1(0, stok, 0, v); } void min_with(int l, int r, long long v) { u1(l, r, 0, stok, 0, v); } void max_with(int l, int r, long long v) { u2(l, r, 0, stok, 0, v); } void range_add(int l, int r, long long v) { u3(l, r, 0, stok, 0, v); } long long query_sum(int l, int r) { return (long long)qu(l, r, 0, stok, 0); } }; struct _1m { segtree_beats a; public: void join(int l, int r, int c, int k) { a.range_add(l, r, k); } void leave(int l, int r, int k) { a.range_add(l, r, -k); a.max_with(l, r, 0); } int service(int shop, int b) { return (a.query_sum(shop, shop) >= b ? 1 : 0); } }; void solve_1m() { _1m ar; ar.a.resize(N); ar.a.init(0); while(Q--) { int t; scanf("%d", &t); //cin >> t; if(t == 1) { int l, r, c, k; scanf("%lld %lld %lld %lld", &l, &r, &c, &k); //cin >> l >> r >> c >> k; ar.join(l, r, c, k); } else if(t == 2) { int l, r, k; scanf("%lld %lld %lld", &l, &r, &k); //cin >> l >> r >> k; ar.leave(l, r, k); } else { int a, b; scanf("%lld %lld", &a, &b); //cin >> a >> b; cout << ar.service(a, b) << "\n"; } } } segtree_beats stb; vector<pair<int, pair<int, int> > > v[4*MAXN]; vector<int> w[4*MAXN]; int p[4*MAXN]; int ti=0; int rp[MAXN]; void update(int l, int r, int constl, int constr, int idx, int c, int k) { if(l<=constl && constr<=r) { v[idx].push_back({ti, {c, k}}); w[idx].push_back(w[idx].empty() ? k : w[idx][w[idx].size() - 1] + k); return; } int mid = (constl+constr) >> 1; if(mid < l || r < constl) update(l, r, mid+1, constr, 2*idx+2, c, k); else if(constr < l || r < mid+1) update(l, r, constl, mid, 2*idx+1, c, k); else { update(l, r, constl, mid, 2*idx+1, c, k); update(l, r, mid+1, constr, 2*idx+2, c, k); } } void build(int l, int r, int idx) { if(l == r) { rp[l] = idx; return; } int mid = (l+r) >> 1; build(l, mid, 2*idx+1); build(mid+1, r, 2*idx+2); p[2*idx+1] = p[2*idx+2] = idx; } void join(int l, int r, int c, int k) { ti++; stb.range_add(l, r, k); update(l, r, 0, MAXN-1, 0, c, k); } void leave(int l, int r, int k) { stb.range_add(l, r, -k); stb.max_with(l, r, 0); } int service(int a, int b) { // log^3 n int cur = rp[a]; vector<int> q; int sum = 0; while(1) { q.push_back(cur); if(w[cur].size()) sum += w[cur][w[cur].size() - 1]; if(cur == 0) break; cur = p[cur]; } b += sum - stb.query_sum(a, a); if(b > sum) return 0; int lb = 0, rb = ti; while(lb < rb) { // log n int mid = (lb+rb) >> 1; int tot = 0; for(int x: q) { // log n if(w[x].empty()) continue; int lb2 = 0, rb2 = w[x].size() - 1; while(lb2 < rb2) { // log n int mid2 = (lb2 + rb2 + 1) >> 1; if(v[x][mid2].first <= mid) { lb2 = mid2; } else { rb2 = mid2 - 1; } } if(v[x][lb2].first <= mid) { tot += w[x][lb2]; } } if(tot >= b) rb = mid; else lb = mid + 1; } for(int x: q) { if(w[x].empty()) continue; int lb2 = 0, rb2 = w[x].size() - 1; while(lb2 < rb2) { // log n int mid2 = (lb2 + rb2 + 1) >> 1; if(v[x][mid2].first <= lb) { lb2 = mid2; } else { rb2 = mid2 - 1; } } if(v[x][lb2].first == lb) { return v[x][lb2].second.first; } } } void solve(int tc) { scanf("%lld %lld %lld", &N, &M, &Q); // cin >> N >> M >> Q; if(M == 1) { // Subtask 4 solve_1m(); return; } stb.resize(N); stb.init(0); build(0, MAXN-1, 0); while(Q--) { int t; scanf("%lld", &t); //cin >> t; if(t == 1) { int l, r, c, k; scanf("%lld %lld %lld %lld", &l, &r, &c, &k); //cin >> l >> r >> c >> k; join(l, r, c, k); } else if(t == 2) { int l, r, k; scanf("%lld %lld %lld", &l, &r, &k); //cin >> l >> r >> k; leave(l, r, k); } else { int a, b; scanf("%lld %lld", &a, &b); //cin >> a >> b; cout << service(a, b) << "\n"; } } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) { solve(i); } }

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

foodcourt.cpp: In member function 'void segtree_beats::pushup(long long int)':
foodcourt.cpp:85:19: warning: unused variable 'max1' [-Wunused-variable]
   85 |         long long max1, max2, maxc;
      |                   ^~~~
foodcourt.cpp:85:25: warning: unused variable 'max2' [-Wunused-variable]
   85 |         long long max1, max2, maxc;
      |                         ^~~~
foodcourt.cpp:85:31: warning: unused variable 'maxc' [-Wunused-variable]
   85 |         long long max1, max2, maxc;
      |                               ^~~~
foodcourt.cpp:86:19: warning: unused variable 'min1' [-Wunused-variable]
   86 |         long long min1, min2, minc;
      |                   ^~~~
foodcourt.cpp:86:25: warning: unused variable 'min2' [-Wunused-variable]
   86 |         long long min1, min2, minc;
      |                         ^~~~
foodcourt.cpp:86:31: warning: unused variable 'minc' [-Wunused-variable]
   86 |         long long min1, min2, minc;
      |                               ^~~~
foodcourt.cpp:87:19: warning: unused variable 'lazy' [-Wunused-variable]
   87 |         long long lazy, sum;
      |                   ^~~~
foodcourt.cpp:87:25: warning: unused variable 'sum' [-Wunused-variable]
   87 |         long long lazy, sum;
      |                         ^~~
foodcourt.cpp:88:19: warning: unused variable 'l' [-Wunused-variable]
   88 |         long long l, r;
      |                   ^
foodcourt.cpp:88:22: warning: unused variable 'r' [-Wunused-variable]
   88 |         long long l, r;
      |                      ^
foodcourt.cpp: In function 'void solve_1m()':
foodcourt.cpp:234:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  234 |         scanf("%d", &t);
      |                ~^   ~~
      |                 |   |
      |                 |   long long int*
      |                 int*
      |                %lld
foodcourt.cpp:234:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~
foodcourt.cpp:238:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |             scanf("%lld %lld %lld %lld", &l, &r, &c, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:244:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |             scanf("%lld %lld %lld", &l, &r, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:250:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  250 |             scanf("%lld %lld", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'long long int service(long long int, long long int)':
foodcourt.cpp:297:17: warning: control reaches end of non-void function [-Wreturn-type]
  297 |     vector<int> q;
      |                 ^
foodcourt.cpp: In function 'void solve(long long int)':
foodcourt.cpp:349:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  349 |     scanf("%lld %lld %lld", &N, &M, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:360:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  360 |         scanf("%lld", &t);
      |         ~~~~~^~~~~~~~~~~~
foodcourt.cpp:364:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  364 |             scanf("%lld %lld %lld %lld", &l, &r, &c, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:370:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  370 |             scanf("%lld %lld %lld", &l, &r, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:376:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  376 |             scanf("%lld %lld", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...