제출 #575836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575836		PedroBigMan	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	34 / 100	341 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;
    }
    
    void prop(node *Y) //how lazy values propagate
    {
        Y->lson->lv=Y->lv&Y->lson->lv; Y->rson->lv=Y->lv&Y->rson->lv;
        Y->lv=neutl;
    }
	
    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.
    {
		if(Y->ind==1) {node * C = CreateCopy(Y,nullptr); Y=C;}
        ll x=Y->l; ll y=Y->r;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(Y);}
        if(Y->lson==nullptr) {node *X=new node(2*Y->ind,neuts,neutl,Y);}
		else {CreateCopy(Y->lson,Y);}
        if(Y->rson==nullptr) {node *X=new node(2*Y->ind+1,neuts,neutl,Y);}
		else {CreateCopy(Y->rson,Y);}
        prop(Y); 
		Y->sv=upval(Y->lson)&upval(Y->rson);
        SV ans = query(a,b,Y->lson)&query(a,b,Y->rson);
        return ans;
	}
    
    void update(LV 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->lv=s&C->lv; 
            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);}
		prop(C);
        update(s,a,b,C->lson,C); update(s,a,b,C->rson,C);
        C->sv=upval(C->lson)&upval(C->rson);
    }
};


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.update(0,0,0,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;
}

컴파일 시 표준 에러 (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:144:37: warning: unused variable 'X' [-Wunused-variable]
  144 |         if(Y->lson==nullptr) {node *X=new node(2*Y->ind,neuts,neutl,Y);}
      |                                     ^
scrivener.cpp:146:37: warning: unused variable 'X' [-Wunused-variable]
  146 |         if(Y->rson==nullptr) {node *X=new node(2*Y->ind+1,neuts,neutl,Y);}
      |                                     ^
scrivener.cpp: In member function 'void PersistentST::update(PersistentST::LV, ll, ll, PersistentST::node*, PersistentST::node*)':
scrivener.cpp:164:37: warning: unused variable 'X' [-Wunused-variable]
  164 |         if(C->lson==nullptr) {node *X=new node(2*C->ind,neuts,neutl,C);}
      |                                     ^
scrivener.cpp:165:37: warning: unused variable 'X' [-Wunused-variable]
  165 |         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