Submission #1725767


Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

string s;
int nxt[27][500011];
const int INF = int(1e9);
int st[19][500011];

void init()
{
	for(int i=0;i<=s.length();i++) st[0][i] = nxt[26][i];
	for(int i=1;i<19;i++)
	{
		for(int j = 0; j <= s.length(); j++)
		{
			st[i][j]=INF;
			if(st[i-1][j]<INF)
			{
				st[i][j]=st[i-1][st[i-1][j]];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>s;
	int n = s.length();
	for(int i=0;i<26;i++) nxt[i][n]=INF;
	nxt[26][n] = n;
	for(int i = n - 1; i >= 0; i--)
	{
		for(int j=0;j<=26;j++) nxt[j][i]=INF;
		nxt[s[i]-'a'][i] = i + 1;
		for(int j = s[i]-'a'+1; j <= 26; j++)
		{
			if(nxt[j-1][i]>=INF) nxt[j][i]=INF;
			else nxt[j][i]=nxt[j-1][nxt[j-1][i]];
		}
		if(nxt[26][i]<INF)
		{
			for(int j=0;j<s[i]-'a';j++)
			{
				nxt[j][i]=nxt[j][nxt[26][i]];
			}
		}
	}
	init();
	int q; cin>>q;
	for(int i=0;i<q;i++)
	{
		int l,r;cin>>l>>r;
		l--;
		int cur=l;
		for(int j=18;j>=0;j--)
		{
			if(st[j][cur]<=r)
			{
				cur=st[j][cur];
			}
		}
		cout<<(cur==r?"Yes":"No")<<'\n';
	}
}

Submission Info

Submission Time
Task C - Robot and String
User vjudge4
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1585 Byte
Status AC
Exec Time 287 ms
Memory 91164 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 67
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt
Case Name Status Exec Time Memory
0_00.txt AC 42 ms 86268 KB
0_01.txt AC 27 ms 86272 KB
0_02.txt AC 27 ms 86272 KB
1_00.txt AC 48 ms 86528 KB
1_01.txt AC 48 ms 86528 KB
1_02.txt AC 287 ms 91036 KB
1_03.txt AC 244 ms 91036 KB
1_04.txt AC 257 ms 91036 KB
1_05.txt AC 266 ms 91036 KB
1_06.txt AC 210 ms 91036 KB
1_07.txt AC 217 ms 91036 KB
1_08.txt AC 234 ms 91036 KB
1_09.txt AC 235 ms 91036 KB
1_10.txt AC 235 ms 91036 KB
1_11.txt AC 235 ms 91036 KB
1_12.txt AC 231 ms 91036 KB
1_13.txt AC 238 ms 91036 KB
1_14.txt AC 245 ms 91036 KB
1_15.txt AC 254 ms 91036 KB
1_16.txt AC 244 ms 91036 KB
1_17.txt AC 259 ms 91036 KB
1_18.txt AC 251 ms 91036 KB
1_19.txt AC 253 ms 91036 KB
1_20.txt AC 257 ms 91036 KB
1_21.txt AC 257 ms 91036 KB
1_22.txt AC 256 ms 91036 KB
1_23.txt AC 255 ms 91164 KB
1_24.txt AC 262 ms 91036 KB
1_25.txt AC 246 ms 91036 KB
1_26.txt AC 233 ms 91036 KB
1_27.txt AC 220 ms 91036 KB
1_28.txt AC 209 ms 91036 KB
1_29.txt AC 213 ms 91036 KB
1_30.txt AC 205 ms 91036 KB
1_31.txt AC 205 ms 91036 KB
1_32.txt AC 207 ms 91036 KB
1_33.txt AC 153 ms 91036 KB
1_34.txt AC 215 ms 90908 KB
1_35.txt AC 227 ms 91036 KB
1_36.txt AC 236 ms 90908 KB
1_37.txt AC 228 ms 91036 KB
1_38.txt AC 241 ms 91036 KB
1_39.txt AC 285 ms 91036 KB
1_40.txt AC 255 ms 91036 KB
1_41.txt AC 232 ms 91036 KB
1_42.txt AC 199 ms 91036 KB
1_43.txt AC 202 ms 91036 KB
1_44.txt AC 188 ms 91036 KB
1_45.txt AC 188 ms 91036 KB
1_46.txt AC 210 ms 91036 KB
1_47.txt AC 174 ms 91036 KB
1_48.txt AC 198 ms 91036 KB
1_49.txt AC 221 ms 91036 KB
1_50.txt AC 245 ms 91036 KB
1_51.txt AC 262 ms 91036 KB
1_52.txt AC 237 ms 91036 KB
1_53.txt AC 186 ms 91036 KB
1_54.txt AC 276 ms 91036 KB
1_55.txt AC 258 ms 91036 KB
1_56.txt AC 230 ms 91036 KB
1_57.txt AC 175 ms 91036 KB
1_58.txt AC 210 ms 91036 KB
1_59.txt AC 207 ms 91036 KB
1_60.txt AC 166 ms 91036 KB
1_61.txt AC 223 ms 91036 KB
1_62.txt AC 188 ms 91036 KB
1_63.txt AC 172 ms 91036 KB