| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1111746 | PagodePaiva | 마상시합 토너먼트 (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const long long MAXN = 5010;
struct Segtremax{
pair <long long, long long> tree[4*MAXN]; long long lazy[4*MAXN];
pair <long long, long long> join(pair <long long, long long> a, pair <long long, long long> b){
if(a.first < b.first) return b;
return a;
}
void unlazy(long long node, long long l, long long 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(long long node, long long l, long long r){
lazy[node] = -1;
if(l == r){
tree[node] = {0, l};
return;
}
long long 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(long long node, long long l, long long r, long long tl, long long tr, long long 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;
}
long long 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 <long long, long long> query(long long node, long long l, long long r, long long tl, long long 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];
long long 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{
long long tree[4*MAXN], lazy[4*MAXN];
long long join(long long a, long long b){
return a+b;
}
void unlazy(long long node, long long l, long long 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(long long node, long long l, long long r){
lazy[node] = -1;
if(l == r){
tree[node] = 1;
return;
}
long long 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(long long node, long long l, long long r, long long tl, long long tr, long long 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;
}
long long 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;
}
long long query(long long node, long long l, long long r, long long tl, long long 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];
long long 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(long long n, long long c, long long r, long long *v, long long *s, long long *e) {
seg.build(1, 1, n);
long long res = 0, pos = 0;
for(long long i = 0;i < n;i++){
seg.update(1, i+1, i+1,1,n, r);
for(long long j = 0;j < i;j++){
seg.update(1, j+1,j+1, 1, n, v[j]);
}
for(long long 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);
long long ansat = 0;
for(long long j = 0;j < c;j++){
long long lt = s[j]+1;
long long rt = e[j]+1;
long long bl = 1, br = n;
long long ansl = 0;
while(bl <= br){
long long 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;
long long ansr = 0;
while(bl <= br){
long long mid = (bl+br)/2;
if(segsum.query(1, 1, mid, 1, n) > rt){
br = mid-1;
}
else{
ansr = mid;
bl = mid+1;
}
}
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;
}