Submission #390384

#	Time	Username	Problem	Language	Result	Execution time	Memory
390384		PedroBigMan	Teams (IOI15_teams)	C++14	0 / 100	1438 ms	524292 KiB

teams

#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 500000000
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007;

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=0;}
        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=0;}
            else
            {
                if(ind%2==0) 
                {
                    par->lson=this;
                    l=par->l; r=(par->l+par->r)/2;
                }
                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=0;}
    PersistentST(ll n)
    {
        N = (ll) 1<<(ll) ceil(log2(n));
        node *X = new node(1,neuts,nullptr);
        X->r=N-1; root.pb(X); anc.pb(0);
    }
    
    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-1; 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, node * Z)
	{
		if(Y->lson==nullptr && Y->rson==nullptr) {return (Y->l);}
		if(Y->lson==nullptr) {if(Z->rson==nullptr) {node *X=new node(2*Z->ind+1,neuts,Z);} return first_index(sum0,cursum,Y->rson,Z->rson);}
		if(Y->rson==nullptr) {if(Z->lson==nullptr) {node *X=new node(2*Z->ind,neuts,Z);} return first_index(sum0,cursum,Y->lson,Z->lson);}
		if(Z->lson==nullptr) {node *X=new node(2*Z->ind,neuts,Z);}
        if(Z->rson==nullptr) {node *X=new node(2*Z->ind+1,neuts,Z);}
		if(cursum+Y->lson->sv.a-Z->lson->sv.a<sum0) {return first_index(sum0,cursum+Y->lson->sv.a-Z->lson->sv.a,Y->rson,Z->rson);}
		else {return first_index(sum0,cursum,Y->lson,Z->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(0);} REP(i,0,N) {oc[ends[i]]++;}
	ll cur=0;
	REP(i,0,N+1)
	{
		decomp.pb({cur,cur+oc[i]-1});
		cur+=oc[i];
	}
	vector<ll> used; REP(i,0,N+1) {used.pb(0);}
	REP(i,0,N) {comp.pb(-1);}
	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+10LL); 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[]) 
{
	sort(K,K+M);
	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==0) {chain.pb({curpos,minend-1}); 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 W = 0; if(minend>=1) {W=check(ind,curpos,0,minend-1);}
		y = S.first_index(needed+W,0,S.root[curpos+1],S.root[ind]);
		if(y>=N) {return 0;}
		chain.pb({curpos,y});
	}
	return 1;
}

Compilation message (stderr)

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-1; 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);}
      |                                     ^
teams.cpp: In member function 'll PersistentST::first_index(ll, ll, PersistentST::node*, PersistentST::node*)':
teams.cpp:143:53: warning: unused variable 'X' [-Wunused-variable]
  143 |   if(Y->lson==nullptr) {if(Z->rson==nullptr) {node *X=new node(2*Z->ind+1,neuts,Z);} return first_index(sum0,cursum,Y->rson,Z->rson);}
      |                                                     ^
teams.cpp:144:53: warning: unused variable 'X' [-Wunused-variable]
  144 |   if(Y->rson==nullptr) {if(Z->lson==nullptr) {node *X=new node(2*Z->ind,neuts,Z);} return first_index(sum0,cursum,Y->lson,Z->lson);}
      |                                                     ^
teams.cpp:145:31: warning: unused variable 'X' [-Wunused-variable]
  145 |   if(Z->lson==nullptr) {node *X=new node(2*Z->ind,neuts,Z);}
      |                               ^
teams.cpp:146:37: warning: unused variable 'X' [-Wunused-variable]
  146 |         if(Z->rson==nullptr) {node *X=new node(2*Z->ind+1,neuts,Z);}
      |                                     ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:182:22: warning: conversion from 'long long int' to 'll' {aka 'int'} may change value [-Wconversion]
  182 |  PersistentST Dummy(N+10LL); S=Dummy;
      |                     ~^~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23