Submission #1196603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196603		CELD_07	Crayfish scrivener (IOI12_scrivener)	C++20	27 / 100	1104 ms	237444 KiB

scrivener

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 998244353
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
#define dgb(x) cout<<#x<<" : "<<x<<"\n"
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
inline ll q(vector<ll>& v1, ll l, ll r){
return (l==0 ? v1[r]: v1[r]-v1[l-1]);
}
string s;
vector<vector<ll>> up;
vector<pair<ll, ll>> v1;
vector<ll> dist;
void Init(){
s="";
vector<pair<ll, ll>>().swap(v1);
vector<ll>().swap(dist);
vector<vector<ll>>().swap(up);
}
void TypeLetter(char L){
s="";
ll o=L-'a', o1=v1.size();
dist.push_back(0);
v1.push_back({1, o});
up.push_back(vector<ll>(24, -1));
if(o1!=0){dist[o1]=dist[o1-1]+1;up[o1][0]=o1-1;}
else dist[o1]=1;
for(int i=1; i<23; i++){
if(up[o1][i-1]!=-1 && up[up[o1][i-1]][i-1]!=-1)up[o1][i]=up[up[o1][i-1]][i-1];
}
}
void UndoCommands(int U){
s="";
ll o1=v1.size();
dist.push_back(0);
v1.push_back({2, U});
up.push_back(vector<ll>(24, -1));
if(o1-U-1>0){up[o1][0]=o1-U-1;dist[o1]=dist[o1-U-1];}
else dist[o1]=0;
for(int i=1; i<23; i++){
if(up[o1][i-1]!=-1 && up[up[o1][i-1]][i-1]!=-1)up[o1][i]=up[up[o1][i-1]][i-1];
}
}
char GetLetter(int P){
P++;
ll o=v1.size();
o--;
for(int i=23; i>=0; i--){
if(up[o][i]!=-1 && dist[up[o][i]]>=P)o=up[o][i];
}
char r1='a'+v1[o].sd;
return r1;
}
/*
int main(){
    //freopen("time.in", "r", stdin);freopen("time.out", "w", stdout);
    //ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    //PRESICION(15)
    //int t;cin>>t;while(t--)
    Init();
    while(1){
    char r, r1;
    ll a;
    cin>>r;
    if(r=='T'){cin>>r1;TypeLetter(r1);}
    else if(r=='P'){cin>>a;cout<<GetLetter(a)<<endl;}
    else {cin>>a;UndoCommands(a);}
    }
}
*/

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