# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
106413 | figter001 | 팀들 (IOI15_teams) | C++17 | 2310 ms | 192888 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 5e5+50;
struct node{
int val,l,r;
node(){
l = r = -1;
val = 0;
}
};
vector<node> seg,tmp;
int idx[nax],n,cnt,k,l,r;
vector<pair<int,int>> p;
void build(int n,int s , int e){
if(s == e){
seg[n].val = 0;
return;
}
seg[n].l = cnt++;
seg[n].r = cnt++;
build(seg[n].l,s,(s+e)/2);
build(seg[n].r,(s+e)/2+1,e);
}
int update(int n , int s , int e,int at){
if(s > at || e < at)
return n;
int newId = cnt++;
seg[newId].val = seg[n].val;
if(s == e){
seg[newId].val++;
return newId;
}
seg[newId].l = update(seg[n].l,s,(s+e)/2,at);
seg[newId].r = update(seg[n].r,(s+e)/2+1,e,at);
seg[newId].val = seg[seg[newId].l].val + seg[seg[newId].r].val;
return newId;
}
void get(int n,int s,int e){
assert(n != -1);
if(l > r || s > r || e < l)
return;
if(s == e){
k -= min(k,seg[n].val);
return;
}
if(s >= l && e <= r){
int le = seg[n].l;
int ri = seg[n].r;
if(seg[le].val <= k){
k -= seg[le].val;
get(ri,(s+e)/2+1,e);
}else{
get(le,s,(s+e)/2);
}
}else{
get(seg[n].l,s,(s+e)/2);
get(seg[n].r,(s+e)/2+1,e);
}
}
void init(int N, int A[], int B[]) {
n = N;
seg.resize(30*n);
for(int i=0;i<n;i++){
p.push_back({A[i],B[i]});
assert(B[i] <= N);
}
cnt = 1;
int lst = cnt;
build(cnt++,1,n);
sort(p.begin(),p.end());
for(int i=0;i<n;i++){
int a = p[i].first;
int b = p[i].second;
idx[a] = cnt;
update(lst,1,n,b);
lst = idx[a];
}
}
int can(int M, int K[]) {
sort(K,K+M);
pair<int,int> lst = {-1,0};
for(int i=0;i<M;i++){
int st = upper_bound(p.begin(),p.end(),make_pair(K[i],(int)1e9)) - p.begin();
if(st == 0)
return 0;
int add = 0;
// cout << i << endl;
if(lst.first != -1){
k = lst.second;
l = K[i-1];
r = K[i] - 1;
get(lst.first,1,n);
add = k;
}
st--;
st = p[st].first;
st = idx[st];
k = K[i] + add;
l = K[i];
r = n;
lst = {st,k};
// cout << l << ' ' << r << ' ' << k << endl;
// cout << k << ' ';
// cout << l << ' ' << r << ' ' << k << endl;
get(st,1,n);
// cout << k << endl;
assert(k >= 0);
if(k != 0)
return 0;
}
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |