Submission #301494

#TimeUsernameProblemLanguageResultExecution timeMemory
301494CodePlatinaComparing Plants (IOI20_plants)C++14
100 / 100
1732 ms85940 KiB
#include "plants.h" #include <iostream> #include <vector> #include <algorithm> #include <string> #include <utility> #define pii pair<int, int> #define piii pair<int, pii> #define pll pair<long long, long long> #define plll pair<long long, pll> #define ff first #define ss second #define ee ss.ff #define rr ss.ss using namespace std; struct Node { pii mn, lazy; }seg[808080]; void prop(int ind) { Node &x = seg[ind << 1], &y = seg[ind << 1 | 1], &nd = seg[ind]; if(nd.lazy.ff) { x.mn.ff += nd.lazy.ff; y.mn.ff += nd.lazy.ff; x.lazy.ff += nd.lazy.ff; y.lazy.ff += nd.lazy.ff; nd.lazy.ff = 0; } if(nd.lazy.ss) { x.mn.ss += nd.lazy.ss; y.mn.ss += nd.lazy.ss; x.lazy.ss += nd.lazy.ss; y.lazy.ss += nd.lazy.ss; nd.lazy.ss = 0; } } void mrge(int ind) { seg[ind].mn = min(seg[ind << 1].mn, seg[ind << 1 | 1].mn); } void init_seg(vector<int> &r, int ind, int s, int e) { if(s + 1 == e) { seg[ind].mn = {r[s], 0}; seg[ind].lazy = {0, 0}; return; } int mid = s + e >> 1; init_seg(r, ind << 1, s, mid); init_seg(r, ind << 1 | 1, mid, e); mrge(ind); } void upd1(int ind, int s, int e, int l, int r, int x) { if(e <= l || r <= s) return; if(l <= s && e <= r) { seg[ind].mn.ff += x; seg[ind].lazy.ff += x; return; } prop(ind); int mid = s + e >> 1; upd1(ind << 1, s, mid, l, r, x); upd1(ind << 1 | 1, mid, e, l, r, x); mrge(ind); } void upd2(int ind, int s, int e, int l, int r, int x) { if(e <= l || r <= s) return; if(l <= s && e <= r) { seg[ind].mn.ss += x; seg[ind].lazy.ss += x; return; } prop(ind); int mid = s + e >> 1; upd2(ind << 1, s, mid, l, r, x); upd2(ind << 1 | 1, mid, e, l, r, x); mrge(ind); } void qr1(vector<int> &ret, int ind, int s, int e, int l, int r) { if(e <= l || r <= s || seg[ind].mn.ff) return; if(s + 1 == e) { ret.push_back(s); return; } prop(ind); int mid = s + e >> 1; qr1(ret, ind << 1, s, mid, l, r); qr1(ret, ind << 1 | 1, mid, e, l, r); } int qr2(int ind, int s, int e) { if(s + 1 == e) return s; prop(ind); int mid = s + e >> 1; if(seg[ind << 1].mn == pii{0, 0}) return qr2(ind << 1, s, mid); else return qr2(ind << 1 | 1, mid, e); } int N, K; int ord[404040]; int rev[202020]; int ils[1616161]; int igr[1616161]; int sls[404040][20]; int sgr[404040][20]; void init3(int ind, int s, int e) { if(s + 1 == e) { ils[ind] = ord[s]; return; } int mid = s + e >> 1; init3(ind << 1, s, mid); init3(ind << 1 | 1, mid, e); ils[ind] = max(ils[ind << 1], ils[ind << 1 | 1]); } void init4(int ind, int s, int e) { if(s + 1 == e) { igr[ind] = ord[s]; return; } int mid = s + e >> 1; init4(ind << 1, s, mid); init4(ind << 1 | 1, mid, e); igr[ind] = min(igr[ind << 1], igr[ind << 1 | 1]); } void upd3(int ind, int s, int e, int l, int r, int x) { if(e <= l || r <= s || ils[ind] <= ord[x]) return; if(s + 1 == e) { sls[s][0] = x; ils[ind] = -1; return; } int mid = s + e >> 1; upd3(ind << 1, s, mid, l, r, x); upd3(ind << 1 | 1, mid, e, l, r, x); ils[ind] = max(ils[ind << 1], ils[ind << 1 | 1]); } void upd4(int ind, int s, int e, int l, int r, int x) { if(e <= l || r <= s || igr[ind] >= ord[x]) return; if(s + 1 == e) { sgr[s][0] = x; igr[ind] = (int)1e9; return; } int mid = s + e >> 1; upd4(ind << 1, s, mid, l, r, x); upd4(ind << 1 | 1, mid, e, l, r, x); igr[ind] = min(igr[ind << 1], igr[ind << 1 | 1]); } void init(int k, vector<int> r) { N = r.size(); K = k; init_seg(r, 1, 0, N); for(int i = 0; i <= N - K; ++i) if(!r[i]) upd2(1, 0, N, i + 1, i + K, 1); for(int i = N - K + 1; i < N; ++i) if(!r[i]) upd2(1, 0, N, i + 1, N, 1), upd2(1, 0, N, 0, K - N + i, 1); for(int i = 0; i < N; ++i) { int t = qr2(1, 0, N); ord[t] = i; vector<int> ls; upd1(1, 0, N, t, t + 1, N); if(t >= K - 1) { upd1(1, 0, N, t - K + 1, t, -1); qr1(ls, 1, 0, N, t - K + 1, t); } else { upd1(1, 0, N, 0, t, -1); upd1(1, 0, N, N - K + t + 1, N, -1); qr1(ls, 1, 0, N, 0, t); qr1(ls, 1, 0, N, N - K + t + 1, N); } if(t <= N - K) upd2(1, 0, N, t + 1, t + K, -1); else { upd2(1, 0, N, t + 1, N, -1); upd2(1, 0, N, 0, K - N + t, -1); } for(int j : ls) { if(j <= N - K) upd2(1, 0, N, j + 1, j + K, 1); else { upd2(1, 0, N, j + 1, N, 1); upd2(1, 0, N, 0, K - N + j, 1); } } } for(int i = 0; i < N; ++i) rev[ord[i]] = i; for(int i = 0; i < N; ++i) ord[i + N] = ord[i]; init3(1, 0, 2 * N); init4(1, 0, 2 * N); for(int i = 0; i <= 2 * N; ++i) sls[i][0] = sgr[i][0] = 2 * N; for(int i = N - 1; i >= 0; --i) { upd3(1, 0, 2 * N, rev[i] - K + 1, rev[i], rev[i]); upd3(1, 0, 2 * N, rev[i] + N - K + 1, rev[i] + N, rev[i] + N); } for(int i = 0; i < N; ++i) { upd4(1, 0, 2 * N, rev[i] - K + 1, rev[i], rev[i]); upd4(1, 0, 2 * N, rev[i] + N - K + 1, rev[i] + N, rev[i] + N); } for(int i = 1; i < 20; ++i) for(int j = 0; j <= 2 * N; ++j) sls[j][i] = sls[sls[j][i - 1]][i - 1], sgr[j][i] = sgr[sgr[j][i - 1]][i - 1]; } int compare_plants(int x, int y) { if(ord[x] < ord[y]) { int tmp = x; for(int i = 19; i >= 0; --i) if(sgr[tmp][i] + K - 1 < y) tmp = sgr[tmp][i]; if(tmp + K - 1 < y) tmp = sgr[tmp][0]; if(tmp != 2 * N && ord[tmp] < ord[y]) return 1; tmp = y; x += N; for(int i = 19; i >= 0; --i) if(sls[tmp][i] + K - 1 < x) tmp = sls[tmp][i]; if(tmp + K - 1 < x) tmp = sls[tmp][0]; if(tmp != 2 * N && ord[tmp] > ord[x]) return 1; } else { int tmp = x; for(int i = 19; i >= 0; --i) if(sls[tmp][i] + K - 1 < y) tmp = sls[tmp][i]; if(tmp + K - 1 < y) tmp = sls[tmp][0]; if(tmp != 2 * N && ord[tmp] > ord[y]) return -1; tmp = y; x += N; for(int i = 19; i >= 0; --i) if(sgr[tmp][i] + K - 1 < x) tmp = sgr[tmp][i]; if(tmp + K - 1 < x) tmp = sgr[tmp][0]; if(tmp != 2 * N && ord[tmp] < ord[x]) return -1; } return 0; }

Compilation message (stderr)

plants.cpp: In function 'void init_seg(std::vector<int>&, int, int, int)':
plants.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd1(int, int, int, int, int, int)':
plants.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd2(int, int, int, int, int, int)':
plants.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void qr1(std::vector<int>&, int, int, int, int, int)':
plants.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'int qr2(int, int, int)':
plants.cpp:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void init3(int, int, int)':
plants.cpp:139:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void init4(int, int, int)':
plants.cpp:153:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd3(int, int, int, int, int, int)':
plants.cpp:169:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd4(int, int, int, int, int, int)':
plants.cpp:185:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  185 |     int mid = s + e >> 1;
      |               ~~^~~
#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...