Submission #760860

#TimeUsernameProblemLanguageResultExecution timeMemory
760860sysiaFire (JOI20_ho_t5)C++17
100 / 100
978 ms151348 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; struct prl{ //parallelogram int x1, x2, y1, y2, val, i; prl(){} prl(int _x1, int _x2, int _y1, int _y2, int _v, int _i): x1(_x1), x2(_x2), y1(_y1), y2(_y2), val(_v), i(_i) {} }; struct Tree{ vector<int>tab, lazy; int size = 1; Tree(int n){ while (size < n) size*=2; tab.assign(2*size, 0); lazy.assign(2*size, 0); } void update(int x, int lx, int rx, int l, int r, int v){ if (lx > r || rx < l) return; if (lx >= l && rx <= r){ tab[x] += v * (rx-lx+1); lazy[x] += v; return; } push(x, lx, rx); int m = (lx+rx)/2; update(2*x, lx, m, l, r, v); update(2*x+1, m+1, rx, l, r, v); tab[x] = tab[2*x] + tab[2*x+1]; } void push(int x, int lx, int rx){ if (!lazy[x] || lx == rx) return; int m = (rx-lx+1)/2; tab[2*x] += lazy[x] * m; tab[2*x+1] += lazy[x] * m; lazy[2*x] += lazy[x]; lazy[2*x+1] += lazy[x]; lazy[x] = 0; } int query(int x, int lx, int rx, int l, int r){ if (lx > r || rx < l) return 0ll; if (lx >= l && rx <= r) return tab[x]; push(x, lx, rx); int m = (lx+rx)/2; return query(2*x, lx, m, l, r) + query(2*x+1, m+1, rx, l, r); } }; int n; int sgn(int x){ if (x >= 0) return 1; return -1; } vector<int>ans; void recsweep(vector<prl>&rec){ int m = (int)rec.size(); vector<T>ord; for (int i = 1; i<=m; i++){ ord.emplace_back(rec[i-1].y1, -i); if (rec[i-1].i >= 0) ord.emplace_back(rec[i-1].y2, i); } //najpierw odejmujemy stare, pozniej dodajemy, pozniej zapytania sort(ord.begin(), ord.end(), [&](auto x, auto y){ if (x.first != y.first) return x.first < y.first; //ten sam x T a = {x.second, rec[abs(x.second)-1].i}; T b = {y.second, rec[abs(y.second)-1].i}; if (a.first >= 0){ if (b.first >= 0){ //oba poczatki --> chcemy najpierw update return a.second < b.second; } else { //poczatek i koniec --> najpierw poczatek return false; } } else { if (b.first >= 0){ return true; } else { //oba konce return a.second > b.second; } } }); Tree t(2*n+3); for (auto &[smiec, id]: ord){ if (id < 0){ id = -id; id--; // cerr << "poczatek "; debug(rec[id].y1, rec[id].x1, rec[id].x2, rec[id].i, rec[id].val); if (rec[id].i < 0){ //query ans[-rec[id].i] += t.query(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2); } else { t.update(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2, rec[id].val); } } else { id--; // cerr << "koniec "; debug(rec[id].y1, rec[id].x1, rec[id].x2, rec[id].i, rec[id].val); if (rec[id].i < 0){ ans[-rec[id].i] += t.query(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2); } else { t.update(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2, -rec[id].val); } } } } void parsweep(vector<prl>&a){ vector<prl>rectangles; for (auto [x1, x2, y1, y2, val, i]: a){ rectangles.emplace_back(x1-y1, x2-y1, y1, y2, val, i); } for (auto [x1, x2, y1, y2, val, i]: rectangles){ debug(x1, x2, y1, y2, val, i); } recsweep(rectangles); } void solve(){ int q; cin >> n >> q; vector<int>a(n+1); for (int i = 1; i<=n; i++) cin >> a[i]; debug(a); stack<int>s; ans.assign(q+1, 0); vector<int>L(n+1, -n); for (int i = 1; i<=n; i++){ while ((int)s.size() && a[s.top()] <= a[i]) s.pop(); if ((int)s.size()) L[i] = s.top(); s.push(i); } vector<int>R(n+1, n+1); while ((int)s.size()) s.pop(); for (int i = n; i>=1; i--) { while ((int)s.size() && a[s.top()] < a[i]) s.pop(); if ((int)s.size()) R[i] = s.top(); s.push(i); } debug(L); debug(R); vector<prl>parallelograms, rectangles; for (int i = 1; i<=n; i++) { parallelograms.emplace_back(L[i]+1, i, 0, R[i]-L[i]-2, a[i], i); //na prawo if (L[i]+1 == i) continue; rectangles.emplace_back(R[i], n+2, R[i]-i, R[i]-L[i]-2, -a[i], i); parallelograms.emplace_back(R[i]+1, n+2, R[i]-i, R[i]-L[i]-2, a[i], i); //na lewo rectangles.emplace_back(-n, i-1, 0, i-L[i]-2, -a[i], i); parallelograms.emplace_back(-n, L[i], 0, i-L[i]-2, a[i], i); } for (int i = 1; i<=q; i++){ int t, l, r; cin >> t >> l >> r; rectangles.emplace_back(l, r, t, t, 0, -i); parallelograms.emplace_back(l, r, t, t, 0, -i); } for (auto [x1, x2, y1, y2, val, i]: parallelograms){ debug(x1, x2, y1, y2, val); } // cerr << "\n"; for (auto [x1, x2, y1, y2, val, i]: rectangles){ debug(x1, x2, y1, y2, val); } // return; recsweep(rectangles); debug(ans); // return; // cerr << "\n"; parsweep(parallelograms); for (int i = 1; i<=q; i++) cout << ans[i] << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }

Compilation message (stderr)

ho_t5.cpp: In function 'void parsweep(std::vector<prl>&)':
ho_t5.cpp:151:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  151 |     for (auto [x1, x2, y1, y2, val, i]: rectangles){
      |               ^~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'void solve()':
ho_t5.cpp:197:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  197 |     for (auto [x1, x2, y1, y2, val, i]: parallelograms){
      |               ^~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:201:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  201 |     for (auto [x1, x2, y1, y2, val, i]: rectangles){
      |               ^~~~~~~~~~~~~~~~~~~~~~~~
#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...