oj.uz

Submission #56481

# Submission time Handle Problem Language Result Execution time Memory
56481 2018-07-11T12:53:00 Z ramchandra Lollipop (POI11_liz) C++14
82 / 100
 2000 ms 52924 KB 
#include <bits/stdc++.h>
#define in(x) ll x;cin>>x;
#define al(x) x.begin(),x.end()
#define vc vector
#define fo(i,a,b) for(ll i=a;i<b;i++)
using namespace std;
using ll = int; // mem
int main(){
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	in(n);in(m);
	//vc<ll> ar(2*n+50,-1);
	//vc<ll> ps(2*n+50,-1);
	//vc<ll> is(2*n+50,-1);
	const ll BIG=2e6+50;
	#define DF(zz) ll zz[BIG];fill(zz,zz+BIG,-1);
	DF(ar);
	DF(ps);
	DF(is);
	DF(ls);
	ll cnt = 0;
	ll fst = -1;
	fo(i,0,n){
		char c;cin>>c;
		bool tp = (c=='T');
		if(fst==-1 && !tp){fst = cnt;}
		ar[cnt]=i;
		ps[i]=cnt;
		cnt++; cnt+=tp;
	}
	if(fst==-1){fst = cnt;}
	ar[cnt] = n;
	ps[n] = cnt;
	ll sz = ar[fst];
	ll c[2] = {2,1};
	fo(i,ar[fst]-1,n){
		ll v = ps[i+1]-fst;
		//cout<<v<<" "<<c[v%2]<<endl;
		for(ll j = max(v,c[v%2]); j <= min((ll)(2*n),v+2*sz); j+=2){
			//assert(is[j] == -1);
			is[j] = i;
			ls[j] = ar[v+fst-j];
			//cerr<<"oh "<<j<<" "<<i<<endl;
		}
		c[v%2] = v+2*sz+2;
	}
	/*fo(i,1,sz+1){
		is[2*i] = ar[fst]-1;
	}*/
	fo(z,0,m){
		in(k);
		ll l=-1,r=-1;
	    if(fst+k<=cnt){
			if(ar[fst+k]==-1){
				l = ar[fst]+1;
				r = ar[fst+k-1];
			}
			else{
				l = ar[fst];
				r = ar[fst+k]-1;
			}
		}
		else {
			if(is[k]!=-1){
				r = is[k];
				//l = ar[ps[r+1]-k];
				l = ls[k];
			}
		}
		if(l!=-1){
			cout<<l+1<<" "<<r+1<<endl;
		}
		else {
			cout<<"NIE"<<endl;
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 33 ms 31720 KB Output is correct
3 Correct 30 ms 31896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31896 KB Output is correct
2 Correct 29 ms 31896 KB Output is correct
3 Correct 32 ms 31896 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31896 KB Output is correct
2 Correct 31 ms 31896 KB Output is correct
3 Correct 63 ms 32040 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 32064 KB Output is correct
2 Correct 43 ms 32064 KB Output is correct
3 Correct 50 ms 32064 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 32268 KB Output is correct
2 Correct 62 ms 32268 KB Output is correct
3 Correct 222 ms 32924 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 32924 KB Output is correct
2 Correct 873 ms 35896 KB Output is correct
3 Correct 364 ms 35896 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 35896 KB Output is correct
2 Correct 264 ms 35896 KB Output is correct
3 Correct 378 ms 35896 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 35896 KB Output is correct
2 Correct 568 ms 35896 KB Output is correct
3 Correct 842 ms 36524 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 39340 KB Output is correct
2 Correct 1223 ms 39340 KB Output is correct
3 Correct 1461 ms 40396 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 40396 KB Output is correct
2 Correct 1364 ms 40396 KB Output is correct
3 Correct 1707 ms 40524 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1955 ms 43820 KB Output is correct
2 Execution timed out 2055 ms 51196 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2028 ms 52924 KB Time limit exceeded
2 Halted 0 ms 0 KB -