| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1085166 | yeediot | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
#define ll long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
const int mxn = 5e5 + 5;
int cnt, rt[mxn];
struct segtree{
struct nde{
int l, r, c;
}seg[mxn << 5];
#define x seg[node]
int build(int l, int r){
int node = ++cnt;
seg[node].c = 0;
if(l == r){
return node;
}
int mm = l + r >> 1;
x.l = build(l, mm), x.r = build(mm + 1, r);
return node;
}
int ins(int from, int l, int r, int p){
int node = ++cnt;
seg[node] = seg[from];
if(l == r){
seg[node].c++;
return node;
}
int mm = l + r >> 1;
if(p <= mm){
x.l = ins(x.l, l, mm, p);
}
else{
x.r = ins(x.r, mm + 1, r, p);
}
x.c = seg[x.l].c + seg[x.r].c;
return node;
}
int kth(int v, int u, int l, int r, int k){
if(l == r){
return l;
}
int mm = l + r >> 1;
int cc = seg[seg[v].r].c - seg[seg[u].r].c;
if(k > cc){
return kth(seg[v].l, seg[u].l, l, mm, k - cc);
}
else{
return kth(seg[v].r, seg[u].r, mm + 1, r, k);
}
}
int bs(int v, int u, int l, int r, int k){
if(l == r){
return seg[v].c - seg[u].c;
}
int mm = l + r >> 1;
if(k > mm){
return bs(seg[v].r, seg[u].r, mm + 1, r, k);
}
else{
return bs(seg[v].l, seg[u].l, l, mm, k) + seg[seg[v].r].c - seg[seg[u].r].c;
}
}
}tr;
int n;
void init(int N, vector<int> a, vector<int> b){
n = N;
rt[0] = tr.build(1, n);
vector<pii>pt;
for(int i = 0; i < n; i++){
pt.pb({a[i], b[i]});
}
sort(all(pt));
int pos = 0;
for(int i = 1; i <= n; i++){
rt[i] = rt[i - 1];
for(; pos < n and pt[pos].F == i; pos++){
tr.ins(rt[i], 1, n, pt[pos].S);
}
}
}
bool can(int m, vector<int>k){
vector<array<int, 3>>st;
st.pb({0, 0, 0});
sort(all(k));
for(auto i : k){
while(sz(st) and st.back()[1] < i){
st.pop_back();
}
int tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
if(tot < 0){
return false;
}
int cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
while(sz(st) and cur > st.back()[1]){
st.pop_back();
cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
}
st.pb({i, cur, tot});
}
return true;
}