Submission #1111752

#TimeUsernameProblemLanguageResultExecution timeMemory
1111752PagodePaivaJousting tournament (IOI12_tournament)C++17
17 / 100
1063 ms1616 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 5010; struct Segtremax{ pair <int, int> tree[4*MAXN]; int lazy[4*MAXN]; pair <int, int> join(pair <int, int> a, pair <int, int> b){ if(a.first < b.first) return b; return a; } void unlazy(int node, int l, int r){ if(lazy[node] == -1) return; tree[node].first = lazy[node]; if(l != r){ lazy[2*node] = max(lazy[2*node], lazy[node]); lazy[2*node+1] = max(lazy[2*node+1], lazy[node]); } lazy[node] = -1; } void build(int node, int l, int r){ lazy[node] = -1; if(l == r){ tree[node] = {0, l}; return; } int mid = (l+r)/2; build(2*node, l, mid); build(2*node+1,mid+1, r); tree[node] = join(tree[2*node], tree[2*node+1]); return; } void update(int node, int l, int r, int tl, int tr, int val){ if(l > r) return; unlazy(node, tl, tr); if(l > tr or tl > r) return; if(l <= tl and tr <= r){ lazy[node] = val; unlazy(node, tl, tr); return; } int mid = (tl+tr)/2; update(2*node, l, r, tl, mid, val); update(2*node+1, l, r, mid+1, tr, val); tree[node] = join(tree[2*node], tree[2*node+1]); return; } pair <int, int> query(int node, int l, int r, int tl, int tr){ if(l > r) return {-1, 0}; unlazy(node, tl, tr); if(l > tr or tl > r) return {-1, 0}; if(l <= tl and tr <= r) return tree[node]; int mid = (tl+tr)/2; return join(query(2*node, l,r,tl, mid), query(2*node+1, l, r, mid+1, tr)); } } seg; struct Segtresum{ int tree[4*MAXN], lazy[4*MAXN]; int join(int a, int b){ return a+b; } void unlazy(int node, int l, int r){ if(lazy[node] == -1) return; tree[node] = (r-l+1)*lazy[node]; if(l != r){ lazy[2*node] = lazy[node]; lazy[2*node+1] = lazy[node]; } lazy[node] = -1; } void build(int node, int l, int r){ lazy[node] = -1; if(l == r){ tree[node] = 1; return; } int mid = (l+r)/2; build(2*node, l, mid); build(2*node+1,mid+1, r); tree[node] = join(tree[2*node], tree[2*node+1]); return; } void update(int node, int l, int r, int tl, int tr, int val){ if(l > r) return; unlazy(node, tl, tr); if(l > tr or tl > r) return; if(l <= tl and tr <= r){ lazy[node] = val; unlazy(node, tl, tr); return; } int mid = (tl+tr)/2; update(2*node, l, r, tl, mid, val); update(2*node+1, l, r, mid+1, tr, val); tree[node] = join(tree[2*node], tree[2*node+1]); return; } int query(int node, int l, int r, int tl, int tr){ if(l > r) return 0; unlazy(node, tl, tr); if(l > tr or tl > r) return 0; if(l <= tl and tr <= r) return tree[node]; int mid = (tl+tr)/2; return join(query(2*node, l,r,tl, mid), query(2*node+1, l, r, mid+1, tr)); } } segsum; int GetBestPosition(int n, int c, int r, int *v, int *s, int *e) { seg.build(1, 1, n); int res = 0, pos = 0; for(int i = 0;i < n;i++){ seg.update(1, i+1, i+1,1,n, r); for(int j = 0;j < i;j++){ seg.update(1, j+1,j+1, 1, n, v[j]); } for(int j = i;j < n-1;j++){ seg.update(1, j+2,j+2,1,n, v[j]); } segsum.update(1,1,n,1,n,1); int ansat = 0; for(int j = 0;j < c;j++){ int lt = s[j]+1; int rt = e[j]+1; int bl = 1, br = n; int ansl = 0; while(bl <= br){ int mid = (bl+br)/2; if(segsum.query(1, 1, mid, 1, n) < lt){ ansl = mid; bl = mid+1; } else{ br = mid-1; } } ansl++; bl = 1, br = n; int ansr = 0; while(bl <= br){ int mid = (bl+br)/2; if(segsum.query(1, 1, mid, 1, n) >= rt){ br = mid-1; } else{ ansr = mid; bl = mid+1; } } ansr++; auto [p, t] = seg.query(1, ansl, ansr, 1, n); if(p == r) ansat++; segsum.update(1, ansl, t-1, 1, n, 0); segsum.update(1, t+1, ansr, 1, n, 0); } if(ansat > res){ pos = i; res = ansat; } } return pos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...