# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
106404 | 2019-04-18T10:45:11 Z | figter001 | 팀들 (IOI15_teams) | C++17 | 860 ms | 194660 KB |
#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){ if(l > r || n == -1) return; if(s > r || e < l) return; if(s == e){ // cout << k << ' ' << seg[n].val << endl; int v = min(k,seg[n].val); k -= v; 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]}); } 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){ cout << 0 << endl; 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; if(k != 0){ cout << 0 << endl; return 0; } } cout << 1 << endl; return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 107 ms | 38892 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 118 ms | 39612 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 860 ms | 194660 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |