Submission #575846

#	Time	Username	Problem	Language	Result	Execution time	Memory
575846		PedroBigMan	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	402 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);}} 

// C++ program to implement persistent segment
// tree.
 
#define MAXN 1000002
 
/* data type for individual
 * node in the segment tree */
struct node
{
    // stores sum of the elements in node
    int val;
 
    // pointer to left and right children
    node* left, *right;
 
    // required constructors........
    node() {}
    node(node* l, node* r, int v)
    {
        left = l;
        right = r;
        val = v;
    }
};
 
// input array
int arr[MAXN];
 
// root pointers for all versions
node* version[MAXN];
 
// Constructs Version-0
// Time Complexity : O(nlogn)
void build(node* n,int low,int high)
{
    if (low==high)
    {
        n->val = arr[low];
        return;
    }
    int mid = (low+high) / 2;
    n->left = new node(NULL, NULL, 0);
    n->right = new node(NULL, NULL, 0);
    build(n->left, low, mid);
    build(n->right, mid+1, high);
    n->val = n->left->val + n->right->val;
}
 
/**
 * Upgrades to new Version
 * @param prev : points to node of previous version
 * @param cur  : points to node of current version
 * Time Complexity : O(logn)
 * Space Complexity : O(logn)  */
void upgrade(node* prev, node* cur, int low, int high,
                                   int idx, int value)
{
    if (idx > high or idx < low or low > high)
        return;
 
    if (low == high)
    {
        // modification in new version
        cur->val = value;
        return;
    }
    int mid = (low+high) / 2;
    if (idx <= mid)
    {
        // link to right child of previous version
        cur->right = prev->right;
 
        // create new node in current version
        cur->left = new node(NULL, NULL, 0);
 
        upgrade(prev->left,cur->left, low, mid, idx, value);
    }
    else
    {
        // link to left child of previous version
        cur->left = prev->left;
 
        // create new node for current version
        cur->right = new node(NULL, NULL, 0);
 
        upgrade(prev->right, cur->right, mid+1, high, idx, value);
    }
 
    // calculating data for current version
    // by combining previous version and current
    // modification
    cur->val = cur->left->val + cur->right->val;
}
 
int query(node* n, int low, int high, int l, int r)
{
    if (l > high or r < low or low > high)
       return 0;
    if (l <= low and high <= r)
       return n->val;
    int mid = (low+high) / 2;
    int p1 = query(n->left,low,mid,l,r);
    int p2 = query(n->right,mid+1,high,l,r);
    return p1+p2;
}
 
/*int main(int argc, char const *argv[])
{
 
 
  
    // creating Version-0
 
    // storing root node for version-0
    version[0] = root;
 
    // upgrading to version-1
    version[1] = new node(NULL, NULL, 0);
    upgrade(version[0], version[1], 0, n-1, 4, 1);
 
    // upgrading to version-2
    version[2] = new node(NULL, NULL, 0);
    upgrade(version[1],version[2], 0, n-1, 2, 10);
 
    cout << "In version 1 , query(0,4) : ";
    cout << query(version[1], 0, n-1, 0, 4) << endl;
 
    cout << "In version 2 , query(3,4) : ";
    cout << query(version[2], 0, n-1, 3, 4) << endl;
 
    cout << "In version 0 , query(0,3) : ";
    cout << query(version[0], 0, n-1, 0, 3) << endl;
    return 0;
}*/


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

void Init() 
{
	N=1000000; REP(i,0,N) {arr[i]=0;}
	node* root = new node(NULL, NULL, 0);
    build(root, 0, MAXN-1); version[0]=root; V=1;
	s.pb(0); com.pb(0);
}

void TypeLetter(char L) 
{
	ll u = (ll) (L-'a');
	version[V] = new node(NULL,NULL,0);
	upgrade(version[V-1],version[V],0,MAXN-1,s.back(),u); 
	s.pb(s.back()+1); com.pb(V); V++;
}

void UndoCommands(int U) 
{
	ll root_ind = com[com.size()-1-U]; ll cursize = s[com.size()-1-U]; s.pb(cursize);
	version[V] = new node(NULL,NULL,0);
	upgrade(version[root_ind],version[V],0,MAXN-1,MAXN-1,0);
	com.pb(V); V++;
}

char GetLetter(int P) 
{
	ll ans = query(version[V-1],0,MAXN-1,P,P);
	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")
      |

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