제출 #541833

#제출 시각아이디문제언어결과실행 시간메모리
541833LucaDantas식물 비교 (IOI20_plants)C++17
0 / 100
47 ms3056 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; constexpr int maxn = 1<<17; int n, k; struct SegmentTree { int tree[maxn<<1], lazy[maxn<<1]; void flush(int node, int i, int j) { if(!lazy[node]) return; if(i != j) { lazy[node<<1] += lazy[node]; lazy[node<<1|1] += lazy[node]; } tree[node] += lazy[node]; lazy[node] = 0; } void build(int node, int i, int j, const vector<int>& r) { if(i == j) return (void)(tree[node] = r[i]); int m = (i+j) >> 1; build(node<<1, i, m, r); build(node<<1|1, m+1, j, r); tree[node] = min(tree[node<<1], tree[node<<1|1]); } int find(int l, int r) { if(l <= r) return find(1, 0, n-1, l, r); int p1 = find(1, 0, n-1, l, n-1); if(p1 != -1) return p1; return find(1, 0, n-1, 0, r); } int find(int node, int i, int j, int l, int r) { flush(node, i, j); if(tree[node] > 0) return -1; if(i == j) return i; int m = (i+j) >> 1; int p1 = find(node<<1, i, m, l, r); if(p1 != -1) return p1; return find(node<<1|1, m+1, j, l, r); } void upd(int l, int r) { if(l <= r) upd(1, 0, n-1, l, r); else upd(1, 0, n-1, l, n-1), upd(1, 0, n-1, 0, r); } void upd(int node, int i, int j, int l, int r) { flush(node, i, j); if(i > r || j < l) return; if(i >= l && j <= r) { lazy[node] = -1; flush(node, i, j); return; } int m = (i+j) >> 1; upd(node<<1, i, m, l, r); upd(node<<1|1, m+1, j, l, r); tree[node] = min(tree[node<<1], tree[node<<1|1]); } void point(int node, int i, int j, int pos) { flush(node, i, j); if(i == j) return (void)(tree[node] = 0x3f3f3f3f); int m = (i+j) >> 1; if(pos <= m) point(node<<1, i, m, pos); else point(node<<1|1, m+1, j, pos); flush(node<<1, i, m); flush(node<<1|1, m+1, j); tree[node] = min(tree[node<<1], tree[node<<1|1]); } } seg; int ordem[maxn]; void init(int K, std::vector<int> r) { n = (int)(r.size()); k = K; seg.build(1, 0, n-1, r); for(int i = 0; i < n; i++) { int mn = seg.find(0, n-1); mn = seg.find((mn - k + 1 + n) % n, mn); // se tiver algum outro cara maximo para a frente dele mas ele estiver olhando pra mim ordem[mn] = i; seg.upd((mn - k + 1 + n) % n, mn); // removo 1 de todo mundo antes de mim seg.point(1, 0, n-1, mn); } } int compare_plants(int x, int y) { return ordem[x] < ordem[y] ? 1 : -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...