Submission #1220610

#TimeUsernameProblemLanguageResultExecution timeMemory
1220610settopCrayfish scrivener (IOI12_scrivener)C++20
100 / 100
555 ms161472 KiB
#include<bits/stdc++.h> #define eb emplace_back #define S second #define dbg(v) cerr << #v << " = " << v << "\n" #define F first #define fall(i,a,n) for(int i=a;i<=n;i++) #define rfall(i,a,n) for(int i=a;i>=n;i--) #define pb push_back #define all(x) x.begin(),x.end() #define lsb(x) (x & -x) #define sz(x) (int)x.size() const int MAXN=1e6+10; const int MAXL=21; const int MOD=998244353; using namespace std; typedef pair<int,int> pii; typedef tuple<int,int,int> trio; int cont=0,s=-1,op[MAXN]={-1},last=0; int sparse[MAXN][MAXL]; set<pair<int,char>> st[MAXN]; void Init(){ return; } void TypeLetter(char L){ s++; cont++; st[s].insert({cont,L}); sparse[cont][0]=last; fall(i,1,MAXL-1) sparse[cont][i]=sparse[sparse[cont][i-1]][i-1]; op[cont]=s; } void UndoCommands(int U) { cont++; sparse[cont][0]=cont-U-1; fall(i,1,MAXL-1) sparse[cont][i]=sparse[sparse[cont][i-1]][i-1]; s=op[sparse[cont][0]]; op[cont]=s; last=cont; } char GetLetter(int P) { int x = cont; for (int i = MAXL - 1; i >= 0; --i) { if (sparse[x][i] != 0 && op[sparse[x][i]] >= P) { x = sparse[x][i]; } } auto it = (--st[P].upper_bound({x, 'z'})); return it->second; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...