제출 #848937

#제출 시각아이디문제언어결과실행 시간메모리
848937mickey080929Sushi (JOI16_sushi)C++17
20 / 100
12044 ms98236 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define sz(x) (int)(x).size() using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<long long, long long> pll; const int inf = 1e9; const int B = 640; struct LazySegmentTree{ int tree[B*4+100]; int lazy[B*4+100]; void init(int n) { fill(tree, tree+n*4+10, inf); fill(lazy, lazy+n*4+10, 0); } void propagate(int node, int s, int e) { if (!lazy[node]) return; tree[node] += lazy[node]; if (s != e) { lazy[node<<1] += lazy[node]; lazy[node<<1|1] += lazy[node]; } lazy[node] = 0; } void update_point(int node, int s, int e, int tar, int val) { propagate(node, s, e); if (s > tar || tar > e) return; if (s == e) { tree[node] = val; return; } int mid = s + e >> 1; update_point(node<<1, s, mid, tar, val); update_point(node<<1|1, mid+1, e, tar, val); tree[node] = min(tree[node<<1], tree[node<<1|1]); } void update_range(int node, int s, int e, int l, int r, int val) { propagate(node, s, e); if (l > e || s > r) return; if (l <= s && e <= r) { lazy[node] = val; propagate(node, s, e); return; } int mid = s + e >> 1; update_range(node<<1, s, mid, l, r, val); update_range(node<<1|1, mid+1, e, l, r, val); tree[node] = min(tree[node<<1], tree[node<<1|1]); } int getmin() { return tree[1]; } }; struct Bucket{ LazySegmentTree seg; priority_queue<int> pq; vector<int> queries; vector<int> a; vector<int> use; vector<int> nxt; void init() { pq = priority_queue<int>(a.begin(), a.end()); use.clear(); int cur = 0; for (int i=0; i<sz(a); i++) { if (cur <= a[i]) { cur = a[i]; use.push_back(i); } } seg.init(sz(use)); nxt.clear(); nxt.resize(sz(use)); cur = 0; for (int i=0; i<sz(use); i++) { int r = sz(a); if (i + 1 < sz(use)) r = use[i+1]; if (use[i] + 1 >= r) { nxt[i] = cur; continue; } int idx = max_element(a.begin()+use[i]+1, a.begin()+r) - a.begin(); if (cur >= a[idx]) { nxt[i] = cur; continue; } cur = a[idx]; nxt[i] = cur; int lo = 0, hi = sz(use) - 1; while (lo < hi) { int mid = lo + hi >> 1; if (a[mid] <= cur) lo = mid + 1; else hi = mid; } seg.update_point(1, 1, sz(use), i+1, i+1 - lo); } } void apply() { vector<int> t; for (auto &x : queries) { int idx = lower_bound(nxt.begin(), nxt.end(), x) - nxt.begin(); seg.update_range(1, 1, sz(use), idx+1, sz(use), -1); if (true || seg.getmin() <= 0) { for (auto &p : use) t.push_back(a[p]); sort(t.begin(), t.end()); assert(sz(t) == sz(use)); for (int i=0; i<sz(use); i++) a[use[i]] = t[i]; t.clear(); int cur = x; for (int i=0; i<sz(a); i++) if (cur <= a[i]) swap(cur, a[i]); init(); } else t.push_back(x); } for (auto &p : use) t.push_back(a[p]); sort(t.begin(), t.end()); for (int i=0; i<sz(use); i++) a[use[i]] = t[i]; queries.clear(); init(); } int Push(int x) { queries.push_back(x); pq.push(x); int t = pq.top(); pq.pop(); return t; } } buc[B]; int n, q; int a[400010]; int query(int l, int r, int x) { int lb = l / B; int rb = r / B; buc[lb].apply(); for (int i=l; i<=min({r, n-1, lb*B+B-1}); i++) { if (x < buc[lb].a[i-lb*B]) { swap(x, buc[lb].a[i-lb*B]); } } buc[lb].init(); if (lb == rb) return x; for (int i=lb+1; i<=rb-1; i++) { x = buc[i].Push(x); } buc[rb].apply(); for (int i=rb*B; i<=min(n-1, r); i++) { if (x < buc[rb].a[i-rb*B]) { swap(x, buc[rb].a[i-rb*B]); } } buc[rb].init(); return x; } int main() { scanf("%d %d", &n, &q); for (int i=0; i<n; i++) { scanf("%d", &a[i]); buc[i/B].a.push_back(a[i]); } for (int i=0; i<=(n-1)/B; i++) { buc[i].init(); } while (q --) { int l, r, x; scanf("%d %d %d", &l, &r, &x); l --; r --; if (l <= r) printf("%d\n", query(l, r, x)); else printf("%d\n", query(0, r, query(l, n-1, x))); } return 0; }

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

sushi.cpp: In member function 'void LazySegmentTree::update_point(int, int, int, int, int)':
sushi.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = s + e >> 1;
      |                   ~~^~~
sushi.cpp: In member function 'void LazySegmentTree::update_range(int, int, int, int, int, int)':
sushi.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = s + e >> 1;
      |                   ~~^~~
sushi.cpp: In member function 'void Bucket::init()':
sushi.cpp:99:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
sushi.cpp: In function 'int main()':
sushi.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sushi.cpp:175:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...