oj.uz

Submission #390363

# Submission time Handle Problem Language Result Execution time Memory
390363 2021-04-15T23:10:56 Z PedroBigMan Teams (IOI15_teams) C++14
77 / 100
 3241 ms 524292 KB 
#include "teams.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class PersistentST //NOTE: If no lazyness is needed, we may remove node copying during queries: remove lines in query section where CreateCopy is written!
{
    public:
    ll N; 
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=0LL;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
    };
    
    SV neuts;
    
    class node
    {
        public:
        ll ind;
        SV sv; 
        ll l,r; //range
        ll rootind;
        
        node *lson, *rson; 
        
        node(ll ind2, SV sv2, node * par) 
        {
            ind=ind2; sv=sv2; lson=nullptr; rson=nullptr; rootind=-1;
            if(ind==1) {l=0LL;}
            else
            {
                if(ind%2==0) 
                {
                    par->lson=this;
                    l=par->l; r=(par->l+par->r)/2LL;
                }
                else 
                {
                    par->rson=this;
                    l=(par->l+par->r+1)/2; r=par->r;
                }
            }
        }
    };
    
    vector<node *> root; //BEWARE: new roots need external initialization of r=N-1
    vector<ll> anc; //anc[i]=j means version i is an update/query from version j
    
	PersistentST() {N=0LL;}
    PersistentST(ll n)
    {
        N = (ll) 1<<(ll) ceil(log2(n));
        node *X = new node(1,neuts,nullptr);
        X->r=N-1LL; root.pb(X); anc.pb(0LL);
    }
    
    node * CreateCopy(node *X, node * par)
    {
        node *ANS = new node(X->ind,X->sv,par); ANS->lson=X->lson; ANS->rson=X->rson;
        if(X->ind==1) 
        {
            ANS->rootind=root.size(); ANS->r=N-1LL; root.pb(ANS); anc.pb(X->rootind);
        }
        return ANS;
    }
	
    SV query(ll a,ll b, node *Y) //range [a,b], current node. initially: query(a,b,root[i]). Will create new version derived from i. Because propagation affects children nodes, we need children to already be copies. To this end, we always copy children aswell. Thus when we traverse a node, it is already copied, we only need to copy the children.
    {
        ll x=Y->l; ll y=Y->r;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return Y->sv;}
        if(Y->lson==nullptr) {node *X=new node(2*Y->ind,neuts,Y);}
        if(Y->rson==nullptr) {node *X=new node(2*Y->ind+1,neuts,Y);}
        SV ans = query(a,b,Y->lson)&query(a,b,Y->rson);
        return ans;
	}
    
    void update(SV s, ll a, node *Y, node * prev) //update LV, range [a,b], current node, current range. initially: update(s,a,b,root[i],nullptr). This will create new root whose ancestor version is version i. prev is used to know who the last newly copied parent is
    {
        ll x=Y->l; ll y=Y->r;
        if(y<a || x>a) {return ;}
		node * C = CreateCopy(Y,prev);
        if(x==a && y==a) 
        {
            C->sv=s&C->sv; 
            return;
        }
        if(C->lson==nullptr) {node *X=new node(2*C->ind,neuts,C);}
        if(C->rson==nullptr) {node *X=new node(2*C->ind+1,neuts,C);}
        update(s,a,C->lson,C); update(s,a,C->rson,C);
        C->sv=C->lson->sv&C->rson->sv;
    }
	
	/*ll first_index(ll sum0,ll cursum,node * Y)
	{
		if(Y->lson==nullptr && Y->rson==nullptr) {return (Y->l);}
		if(Y->lson==nullptr) {return first_index(sum0,cursum,Y->rson);}
		if(Y->rson==nullptr) {return first_index(sum0,cursum,Y->lson);}
		if(cursum+Y->lson->sv.a<sum0) {return first_index(sum0,cursum+Y->lson->sv.a,Y->rson);}
		else {return first_index(sum0,cursum,Y->lson);}
	}*/
};

ll N; vector<pl> p;
vector<pl> decomp; vector<ll> comp;
PersistentST S;

ll check(ll A, ll B, ll C, ll D) //how many intervals with begin in [A,B] end in [C,D] (C, D new coordinates)
{
	return (S.query(C,D,S.root[B+1]).a - S.query(C,D,S.root[A]).a);
}

void init(int n, int A[], int B[])
{
	N=(ll) n; REP(i,0,N) {p.pb({(ll) A[i], (ll) B[i]});}
	//decomp[i] = {l,r} means ending coord i has decompressed coordinates [l,r]. comp[i]=j means decompressed coordinate i was previously real coordinate j
	//bounds[i] = {l,r} means first index: p[index].ff>=i is l, first index: p[index].ff>i is r default values are N
	vector<ll> ends; REP(i,0,N) {ends.pb((ll) B[i]);} sort(whole(ends)); vector<ll> oc; REP(i,0,N+1) {oc.pb(0LL);} REP(i,0,N) {oc[ends[i]]++;}
	ll cur=0LL;
	REP(i,0,N+1)
	{
		decomp.pb({cur,cur+oc[i]-1LL});
		cur+=oc[i];
	}
	vector<ll> used; REP(i,0,N+1) {used.pb(0LL);}
	REP(i,0,N) {comp.pb(-1LL);}
	REP(i,0,N)
	{
		ll endval = p[i].ss; 
		p[i].ss = decomp[endval].ff+used[endval];
		used[endval]++; comp[p[i].ss]=endval;
	}
	sort(whole(p));
	PersistentST Dummy(N); S=Dummy;
	REP(i,0,N)
	{
		S.update(1,p[i].ss,S.root.back(),nullptr);
	}
	//NOTE: S.root[i+1] relates to update after position i in [0,N-1]
	return ;
}

int can(int M, int k[]) 
{
	vector<ll> K; REP(i,0,M) {K.pb((ll) k[i]);} sort(whole(K));
	vector<pl> chain; //elements of chain are pairs {pos,val} meaning seg tree at index pos in [0,N-1] was ripped of all elements until val (val in new coordinates)
	REP(i,0,M)
	{
		ll minend = decomp[K[i]].ff; ll needed=K[i];
		ll curpos = (ll) (lower_bound(whole(p),(pl){K[i]+1,0}) - p.begin()) -1; //index of new seg tree we're removing from
		while(chain.size()>0 && chain.back().ss<minend) {chain.pop_back();}
		ll ind, x, newendings, y;
		while(needed>0 && chain.size()>0)
		{
			ind = chain.back().ff; x = chain.back().ss; //at index of p ind, all endings until x were removed. Thus the endings in [minend,x] there are at curpos are the number of endings in [minend,x] with index in array p in [ind+1,curpos]
			newendings = check(ind+1,curpos,minend,x);
			if(needed>=newendings) 
			{
				minend=x+1;
				chain.pop_back();
				needed-=newendings;
				continue;
			}
			else {break;}
		}
		if(needed==0LL) {chain.pb({curpos,minend-1LL}); continue;}
		ind=0;
		if(chain.size()>0) {ind=chain.back().ff+1;}
		//we need to find min y such that there are exactly needed endings in [ind,curpos] with endings in [minend,y]. 
		ll lo = minend; ll hi = N-1; ll mid;
		while(lo<hi)
		{
			mid =(lo+hi)/2LL;
			newendings = check(ind,curpos,minend,mid);
			if(newendings<needed) {lo=mid+1;} else {hi=mid;}
		}
		y=lo;
		newendings = check(ind,curpos,minend,y);
		if(newendings!=needed) {return 0;}
		chain.pb({curpos,y});
	}
	return 1;
}

Compilation message

teams.cpp: In constructor 'PersistentST::PersistentST(ll)':
teams.cpp:100:15: warning: conversion from 'long long int' to 'll' {aka 'int'} may change value [-Wconversion]
  100 |         X->r=N-1LL; root.pb(X); anc.pb(0LL);
      |              ~^~~~
teams.cpp: In member function 'PersistentST::node* PersistentST::CreateCopy(PersistentST::node*, PersistentST::node*)':
teams.cpp:108:35: warning: conversion from 'std::vector<PersistentST::node*>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
  108 |             ANS->rootind=root.size(); ANS->r=N-1LL; root.pb(ANS); anc.pb(X->rootind);
      |                          ~~~~~~~~~^~
teams.cpp:108:47: warning: conversion from 'long long int' to 'll' {aka 'int'} may change value [-Wconversion]
  108 |             ANS->rootind=root.size(); ANS->r=N-1LL; root.pb(ANS); anc.pb(X->rootind);
      |                                              ~^~~~
teams.cpp: In member function 'PersistentST::SV PersistentST::query(ll, ll, PersistentST::node*)':
teams.cpp:118:37: warning: unused variable 'X' [-Wunused-variable]
  118 |         if(Y->lson==nullptr) {node *X=new node(2*Y->ind,neuts,Y);}
      |                                     ^
teams.cpp:119:37: warning: unused variable 'X' [-Wunused-variable]
  119 |         if(Y->rson==nullptr) {node *X=new node(2*Y->ind+1,neuts,Y);}
      |                                     ^
teams.cpp: In member function 'void PersistentST::update(PersistentST::SV, ll, PersistentST::node*, PersistentST::node*)':
teams.cpp:134:37: warning: unused variable 'X' [-Wunused-variable]
  134 |         if(C->lson==nullptr) {node *X=new node(2*C->ind,neuts,C);}
      |                                     ^
teams.cpp:135:37: warning: unused variable 'X' [-Wunused-variable]
  135 |         if(C->rson==nullptr) {node *X=new node(2*C->ind+1,neuts,C);}
      |                                     ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct
13 Correct 4 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 99580 KB Output is correct
2 Correct 243 ms 99464 KB Output is correct
3 Correct 222 ms 99644 KB Output is correct
4 Correct 242 ms 99888 KB Output is correct
5 Correct 177 ms 102280 KB Output is correct
6 Correct 172 ms 100792 KB Output is correct
7 Correct 165 ms 99512 KB Output is correct
8 Correct 171 ms 99512 KB Output is correct
9 Correct 530 ms 107984 KB Output is correct
10 Correct 386 ms 107448 KB Output is correct
11 Correct 192 ms 102920 KB Output is correct
12 Correct 163 ms 99744 KB Output is correct
13 Correct 205 ms 99468 KB Output is correct
14 Correct 191 ms 99468 KB Output is correct
15 Correct 216 ms 99512 KB Output is correct
16 Correct 211 ms 99584 KB Output is correct
17 Correct 171 ms 99644 KB Output is correct
18 Correct 172 ms 99532 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 99552 KB Output is correct
2 Correct 240 ms 99724 KB Output is correct
3 Correct 2792 ms 112640 KB Output is correct
4 Correct 225 ms 99768 KB Output is correct
5 Correct 1491 ms 102728 KB Output is correct
6 Correct 1314 ms 102804 KB Output is correct
7 Correct 180 ms 99508 KB Output is correct
8 Correct 1031 ms 102800 KB Output is correct
9 Correct 532 ms 107984 KB Output is correct
10 Correct 1374 ms 108288 KB Output is correct
11 Correct 1807 ms 108216 KB Output is correct
12 Correct 2536 ms 108008 KB Output is correct
13 Correct 3241 ms 109060 KB Output is correct
14 Correct 3124 ms 111636 KB Output is correct
15 Correct 1062 ms 100000 KB Output is correct
16 Correct 1057 ms 99896 KB Output is correct
17 Correct 1057 ms 99892 KB Output is correct
18 Correct 1120 ms 100244 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1408 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -