oj.uz

Submission #390383

# Submission time Handle Problem Language Result Execution time Memory
390383 2021-04-16T00:37:39 Z PedroBigMan Teams (IOI15_teams) C++14
77 / 100
 1390 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 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;}
		newendings = check(ind,curpos,0,y);
		if(newendings!=W+needed) {return 0;}
		chain.pb({curpos,y});
	}
	return 1;
}

Compilation message

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
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 208 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 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 368 KB Output is correct
14 Correct 1 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 316 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 228 ms 99580 KB Output is correct
2 Correct 225 ms 99476 KB Output is correct
3 Correct 226 ms 99720 KB Output is correct
4 Correct 235 ms 99472 KB Output is correct
5 Correct 166 ms 99512 KB Output is correct
6 Correct 163 ms 99512 KB Output is correct
7 Correct 162 ms 99512 KB Output is correct
8 Correct 167 ms 99556 KB Output is correct
9 Correct 217 ms 106156 KB Output is correct
10 Correct 189 ms 103664 KB Output is correct
11 Correct 161 ms 99712 KB Output is correct
12 Correct 161 ms 99636 KB Output is correct
13 Correct 208 ms 99464 KB Output is correct
14 Correct 188 ms 99492 KB Output is correct
15 Correct 210 ms 99512 KB Output is correct
16 Correct 210 ms 99512 KB Output is correct
17 Correct 168 ms 99512 KB Output is correct
18 Correct 175 ms 99512 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 99472 KB Output is correct
2 Correct 230 ms 99588 KB Output is correct
3 Correct 621 ms 108856 KB Output is correct
4 Correct 230 ms 99544 KB Output is correct
5 Correct 301 ms 99632 KB Output is correct
6 Correct 310 ms 99768 KB Output is correct
7 Correct 171 ms 99548 KB Output is correct
8 Correct 257 ms 99584 KB Output is correct
9 Correct 217 ms 106140 KB Output is correct
10 Correct 309 ms 106824 KB Output is correct
11 Correct 356 ms 106896 KB Output is correct
12 Correct 461 ms 107056 KB Output is correct
13 Correct 760 ms 106936 KB Output is correct
14 Correct 740 ms 108216 KB Output is correct
15 Correct 304 ms 99640 KB Output is correct
16 Correct 300 ms 99720 KB Output is correct
17 Correct 274 ms 99768 KB Output is correct
18 Correct 278 ms 99668 KB Output is correct

Subtask #4
0 / 23.0

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