| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 416793 | FerThugGato12500 | 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 "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int lmt = 500005;
const int MOD = 1000000007;
#define f first
#define S second
#define ll long long
#define ld long double
#define ull unsigned long long
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define for1(i, n) for(int i = 1; i < int(n); i++)
#define forv(i,a,n) for(int i = int(a); i < int(n); i++)
#define rof(i, n) for(int i = int(n); i >= 0; i--)
#define rofv(i,a,n) for(int i = int(n); i >= int(a); i--)
#define pb push_back
#define ins insert
#define pai pair<int, int>
#define pal pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define vld vector<long double>
struct wer{
int A, B;
};
bool operator < (const wer &a, const wer &b){
return a.A < b.A;
}
int n;
wer p[lmt];
vi st[lmt*4];
int lessa[lmt*4];
struct ST{
void build(){
build(0,n-1,0);
return;
}
void build(int ini, int fin, int ind){
if(ini==fin){
st[ind].pb(p[ini].B);
return;
}
int mit = (ini+fin)/2, ls = (ind*2)+1, rs = (ind*2)+2;
build(ini, mit, ls);
build(mit+1, fin, rs);
int a = 0, b = 0;
while(a<st[ls].size() || b<st[rs].size()){
if(b==st[rs].size() || st[ls][a]>=st[rs][b]){
st[ind].pb(st[ls][a]);
a++;
}else{
st[ind].pb(st[rs][b]);
b++;
}
}
return;
}
int x, v, l;
bool query(int stf, int stf2){
if(stf2==-1){
lessa[0]=0;
return false;
}
x = v = stf; l = stf2;
query(0, n-1, 0);
if(v>0){
lessa[0] = 0;
return false;
}
return true;
}
int find(int ind, int X){
int ini = lessa[ind], fin = st[ind].size()-1;
if(st[ind][ini]<x){
return lessa[ind]-1;
}
while(ini+1<fin){
int mit = (ini+fin)/2;
if(st[ind][mit]>=X){
ini = mit;
}else{
fin = mit-1;
}
}
if(st[ind][fin]>=X){
return fin;
}
return ini;
}
void upd(int ind){
int ls = (ind*2)+1, rs = (ind*2)+2;
if(lessa[ind]==0) {
lessa[ls] = lessa[rs] = 0;
return;
}
int V = lessa[ind];
int t = st[ind][lessa[ind]-1];
int c = find(rs, t)+1;
if(c<=V){
lessa[rs] = c;
lessa[ls] = V-c;
}else{
lessa[rs] = V;
}
return;
}
void query(int ini, int fin, int ind){
int mit = (ini+fin)/2, ls = (ind*2)+1, rs = (ind*2)+2;
if(ini>l||fin<0){
return;
}
if(ini>=0 && fin<=l){
if(v==0) return;
int r = (find(ind, x) - lessa[ind])+1;
if(r<=v){
v-=r;
lessa[ind] += r;
}else{
lessa[ind] += v;
v=0;
}
return;
}
upd(ind);
query(mit+1, fin, rs);
query(ini, mit, ls);
return;
}
};
int alierputoxd[lmt];
ST mqun;
void init(int N, vector<int> A, vector<int> B){
n=N;
forn(i, n) p[i].A = A[i];
forn(i, n) p[i].B = B[i];
sort(p, p+n);
forn(i, n-1){
if(p[i].A != p[i+1].A){
alierputoxd[p[i].A] = i;
}
}
alierputoxd[p[n-1].A] = n-1;
alierputoxd[0] = -1;
for1(i,n+1){
if(!alierputoxd[i] && !(i == 1 && p[0].A==1)){
alierputoxd[i] = alierputoxd[i-1];
}
}
mqun.build();
return;
}
bool can(int k, vector<int> Q){
sort(Q.begin(), Q.end());
reverse(Q.begin(), Q.end());
for(int x: Q){
if(!mqun.query(x, alierputoxd[x])){
return false;
}
}
return true;
}