# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
56470 |
2018-07-11T12:36:52 Z |
ramchandra |
Lollipop (POI11_liz) |
C++14 |
|
2000 ms |
35092 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);
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;
//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];
}
}
if(l!=-1){
cout<<l+1<<" "<<r+1<<endl;
}
else {
cout<<"NIE"<<endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
25 ms |
23908 KB |
Output is correct |
3 |
Correct |
20 ms |
23908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23908 KB |
Output is correct |
2 |
Correct |
21 ms |
23952 KB |
Output is correct |
3 |
Correct |
22 ms |
24016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
24016 KB |
Output is correct |
2 |
Correct |
27 ms |
24016 KB |
Output is correct |
3 |
Correct |
53 ms |
24100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
24120 KB |
Output is correct |
2 |
Correct |
50 ms |
24132 KB |
Output is correct |
3 |
Correct |
50 ms |
24164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
24320 KB |
Output is correct |
2 |
Correct |
70 ms |
24320 KB |
Output is correct |
3 |
Correct |
233 ms |
25244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
25244 KB |
Output is correct |
2 |
Correct |
759 ms |
28044 KB |
Output is correct |
3 |
Correct |
511 ms |
28044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
28044 KB |
Output is correct |
2 |
Correct |
219 ms |
28044 KB |
Output is correct |
3 |
Correct |
412 ms |
28044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
622 ms |
28044 KB |
Output is correct |
2 |
Correct |
708 ms |
28044 KB |
Output is correct |
3 |
Correct |
760 ms |
28588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1324 ms |
31504 KB |
Output is correct |
2 |
Correct |
1297 ms |
31504 KB |
Output is correct |
3 |
Correct |
1420 ms |
32680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
992 ms |
32680 KB |
Output is correct |
2 |
Correct |
1366 ms |
32680 KB |
Output is correct |
3 |
Correct |
1879 ms |
32680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2037 ms |
34836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2036 ms |
35092 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |