| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 40537 | pulgares | Nice sequence (IZhO18_sequence) | C++14 | 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.
//marico el que lo lea
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
void fastIO() {
std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
#define FOR(i,f,t) for(int i=f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=f; i>(int)t; i--)
#define FORE(i,c) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define all(obj) obj.begin(), obj.end()
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define ms2(obj, val, sz) memset(obj, val, sizeof(obj[0])*sz)
#define fst first
#define snd second
template<typename T, typename U> inline void mnze(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void mxze(T &x, U y) { if(x < y) x = y; }
void _scan( int &x ) { scanf("%d",&x); }
void _scan( long long &x ) { scanf("%lld",&x); }
void _scan( double &x ) { scanf("%lf",&x); }
void _scan( char &x ) { scanf(" %c",&x); }
void _scan( char *x ) { scanf("%s",x); }
void scan() {}
template<typename T, typename... U>
void scan( T& head, U&... tail ) { _scan(head); scan(tail...);}
template<typename T> void _dbg(const char* sdbg, T h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename T, typename... U> void _dbg(const char* sdbg, T h, U... t) {
while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(_i, (x)) cerr <<*_i <<", "; cerr <<"\n"; }}
#define debuga(x, sz) {{cerr <<#x <<" = "; FOR(_i, 0, sz) cerr << x[_i] <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define debuga(x, sz)
#define cerr if(0)cout
#endif
struct stnode{
int sum;
stnode *l=NULL, *r=NULL;
void merge(){sum = l->sum + r->sum;}
void upd(int x){sum += x;}
};
typedef stnode* pstnode;
vector<pstnode> root, all;
vector<stnode> nodes;
int N;
inline void clear(){
all.clear(); root.clear();
nodes.clear();
}
inline pstnode new_node(){
all.pb(new stnode());
return all.back();
}
void init(int n){
root.pb(new_node());
N = n;
}
void build(){
root[0]->sum = 0;
root[0]->l=root[0];
root[0]->r=root[0];
}
inline pstnode erase(int b, pstnode v, int l, int r){
if(r<=b) return root[0];
int M = (l+r)>>1;
pstnode u = new_node();
if(b<=M){
u->r = v->r;
u->l = erase(b, v->l, l, M);
}else{
u->l = root[0];
u->r = erase(b, v->r, M, r);
}
u->merge();
return u;
}
// erase all elements < b in ver (used)
inline int erase(int b, int ver){
root.pb(erase(b, root[ver], 0, N));
return root.size()-1;
}
int KK;
// we are always in nodes were we have enough.
inline pstnode bs(pstnode v, pstnode usedv, int l, int r){
int lft = v->sum - usedv->sum;
if(lft == KK){
KK=0;
return v;
}
pstnode u = new_node();
u->sum = usedv->sum;
if(r-l==1){
u->sum += KK;
KK=0;
return u;
}
int M = (l+r)>>1;
int llft = v->l->sum - usedv->l->sum;
if(llft >= KK){
u->r = usedv->r;
u->l = bs(v->l, usedv->l, l, M);
}else{
KK -= llft;
u->l = v->l;
u->r = bs(v->r, usedv->r, M, r);
}
u->merge();
return u;
}
inline bool bs(int k, int ver, int &usedver){
KK = k;
//debug(k);
if(root[ver]->sum - root[usedver]->sum < KK) return false;
//debug(root[ver]->sum, root[usedver]->sum);
root.pb( bs(root[ver], root[usedver], 0, N) );
usedver = root.size()-1;
//debug(root[usedver]->sum);
return KK==0;
}
inline pstnode update(int p, int x, pstnode v, int l, int r){
pstnode u = new_node();
if(r - l < 2){
u->sum = v->sum;
u->upd(x);
return u;
}
int M = (l+r)>>1;
u->l = v->l, u->r = v->r;
if(p < M) u->l = update(p, x, v->l, l, M);
else u->r = update(p, x, v->r, M, r);
u->merge();
return u;
}
inline int update(int p, int x, int ver){
root.pb(update(p, x, root[ver], 0, N));
return root.size()-1;
}
///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
const int MAXN = 5e5+5;
int A[MAXN], B[MAXN], BtoB[MAXN];
vi AtoB[MAXN];
vi strt;
int M, K[MAXN];
int solve(){
int ans = 1;
sort(K, K+M);
int ni = all.size();
//debug(ni);
int usedrt = 0;
FOR(i,0,M && ans){
usedrt = erase(K[i], usedrt);
ans &= bs(K[i], strt[K[i]], usedrt);
}
FOR(i,ni,all.size()) delete all[i];
all.resize(ni);
return ans;
}
void pre(){
FOR(i,0,N){
AtoB[A[i]].pb(B[i]);
BtoB[B[i]]++;
}
N++;
init(N);
build();
strt.pb(0);
FOR(i,1,N){
int nxt = strt.back();
if(AtoB[i].size()){
int b = AtoB[i][0], cnt=1;
FOR(j,1,AtoB[i].size()){
if(AtoB[i][j]==b) cnt++;
else{
nxt = update(b, cnt, nxt);
cnt=1;
b=AtoB[i][j];
}
}
nxt = update(b, cnt, nxt);
}
//for(int b : AtoB[i]) nxt = update(b, 1, nxt);
if(BtoB[i-1]) nxt = update(i-1, -BtoB[i-1], nxt);
//debug(BtoB[i-1]);
strt.pb(nxt);
//debug(st.root[strt[i]]->sum);
}
}
void init(int NN, int *AA, int *BB){
N=NN;
FOR(i,0,N) A[i]=AA[i];
FOR(i,0,N) B[i]=BB[i];
pre();
}
int can(int MM, int *KK){
M = MM;
FOR(i,0,M) K[i]=KK[i];
return solve();
}