Submission #575840

#	Time	Username	Problem	Language	Result	Execution time	Memory
575840		PedroBigMan	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	401 ms	262144 KiB

scrivener

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#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 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
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=0;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV neuts; LV neutl;
    
    class node
    {
        public:
        ll ind;
        SV sv; LV lv;
        ll l,r; //range
        ll rootind;
        
        node *lson, *rson; 
        
        node(ll ind2, SV sv2, LV lv2, node * par) 
        {
            ind=ind2; sv=sv2; lv=lv2; 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
    
    SV upval(node *X) //how lazy values modify a seg value inside a node, c=current node
    {
        SV ANS((X->sv).a+(X->r-X->l+1)*(X->lv).a);
        return ANS;
    }
    
	PersistentST() {N=0;}
    PersistentST(ll n)
    {
        N = (ll) 1<<(ll) ceil(log2(n));
        node *X = new node(1,neuts,neutl,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,X->lv,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,neutl,Y);}
        if(Y->rson==nullptr) {node *X=new node(2*Y->ind+1,neuts,neutl,Y);}
        SV ans = query(a,b,Y->lson)&query(a,b,Y->rson);
        return ans;
	}
    
    void update(SV s, ll a, ll b, 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>b) {return ;}
		node * C = CreateCopy(Y,prev);
        if(x>=a && y<=b) 
        {
            C->sv=s;
            return;
        }
        if(C->lson==nullptr) {node *X=new node(2*C->ind,neuts,neutl,C);}
        if(C->rson==nullptr) {node *X=new node(2*C->ind+1,neuts,neutl,C);}
        update(s,a,b,C->lson,C); update(s,a,b,C->rson,C);
    }
};


ll N;
PersistentST S;
vector<ll> com; //last index of Seg Tree after command i
vector<ll> s; //size of word after command i

void Init() 
{
	N=1000000;
	S = *(new PersistentST(N));
	s.pb(0); com.pb(0);
}

void TypeLetter(char L) 
{
	ll u = (ll) (L-'a');
	S.update(u,s.back(),s.back(),S.root.back(),nullptr);
	s.pb(s.back()+1); com.pb(S.root.size()-1);
}

void UndoCommands(int U) 
{
	ll root_ind = com[com.size()-1-U]; ll cursize = s[com.size()-1-U]; s.pb(cursize);
	S.CreateCopy(S.root[root_ind], nullptr);
	com.pb(S.root.size()-1);
}

char GetLetter(int P) 
{
	ll ans = S.query(P,P,S.root.back()).a;
	char c_ans = (char) ('a' + ans);
	return c_ans;
}

Compilation message (stderr)

scrivener.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
scrivener.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
scrivener.cpp: In member function 'PersistentST::SV PersistentST::query(ll, ll, PersistentST::node*)':
scrivener.cpp:137:37: warning: unused variable 'X' [-Wunused-variable]
  137 |         if(Y->lson==nullptr) {node *X=new node(2*Y->ind,neuts,neutl,Y);}
      |                                     ^
scrivener.cpp:138:37: warning: unused variable 'X' [-Wunused-variable]
  138 |         if(Y->rson==nullptr) {node *X=new node(2*Y->ind+1,neuts,neutl,Y);}
      |                                     ^
scrivener.cpp: In member function 'void PersistentST::update(PersistentST::SV, ll, ll, PersistentST::node*, PersistentST::node*)':
scrivener.cpp:153:37: warning: unused variable 'X' [-Wunused-variable]
  153 |         if(C->lson==nullptr) {node *X=new node(2*C->ind,neuts,neutl,C);}
      |                                     ^
scrivener.cpp:154:37: warning: unused variable 'X' [-Wunused-variable]
  154 |         if(C->rson==nullptr) {node *X=new node(2*C->ind+1,neuts,neutl,C);}
      |                                     ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40