#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 120005;
struct sparse{
vector<vector<int>> mn , mx;
vector<int> logs , v;
int n;
void build(){
int n = v.size();
for(int i=0;i<n;i++) mn[i][0] = mx[i][0] = v[i];
for(int k=1;k<30;k++){
for(int i=0;i+(1<<k)-1<n;i++) mn[i][k] = min(mn[i][k-1],mn[i+(1<<k-1)][k-1]), mx[i][k] = max(mx[i][k-1],mx[i+(1<<k-1)][k-1]);
}
for(int i=2;i<=n;i++) logs[i] = logs[i>>1] + 1;
}
sparse(vector<int> _v){
v = _v;
n = v.size();
mn.resize(n,vector<int>(30)), mx.resize(n,vector<int>(30)), logs.resize(n+1);
build();
}
int mxQ(int l,int r){
if(l > r) return 0;
int sz = r - l + 1;
int lg = logs[sz];
return max(mx[l][lg],mx[r-(1<<lg)+1][lg]);
}
int mnQ(int l,int r){
if(l > r) return 0;
int sz = r - l + 1;
int lg = logs[sz];
return min(mn[l][lg],mn[r-(1<<lg)+1][lg]);
}
};
void solve(){
int n,q;
cin>>n>>q;
vector<array<int,3>> qs;
vector<int> time(n-1);
int cnt = 0;
for(int qq=0;qq<n+q-1;qq++){
char c;
int a,b=0;
cin>>c>>a;
a --;
if(c != 'C') cin>>b,b --;
qs.push_back({(int)c,a,b});
if(c == 'S') time[min(a,b)] = cnt;
cnt ++;
}
vector<int> dif(n-2);
for(int i=0;i<n-2;i++) dif[i] = time[i] - time[i+1];
sparse s1(time);
sparse s2(dif);
cnt = 0;
for(auto [c,a,b] : qs){
if(c == 'S') {cnt++;continue;}
if(c == 'Q'){
if(a == b) cout<<"yes"<<endl;
else if(a < b){
if(s1.mxQ(a,b-1) <= cnt && s2.mnQ(a,b-2) >= 0) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
else {
swap(a,b);
if(s1.mxQ(a,b-1) <= cnt && s2.mxQ(a,b-2) <= 0) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
else {
int l=a;
int r=n-1;
int sz1 = 0 , sz2 = 0;
while(l<=r){
int md = l + r >> 1;
if(s1.mxQ(a,md-1) <= cnt && s2.mnQ(a,md-2) >= 0) sz1 = md - a, l = md+1;
else r = md-1;
}
l=0, r=a;
while(l<=r){
int md = l + r >> 1;
if(s1.mxQ(md,a-1) <= cnt && s2.mxQ(md,a-2) <= 0) sz2 = a - md, r = md-1;
else l = md+1;
}
cout<<sz1 + sz2 + 1<<endl;
}
cnt ++;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
servers.cpp: In member function 'void sparse::build()':
servers.cpp:14:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
14 | for(int i=0;i+(1<<k)-1<n;i++) mn[i][k] = min(mn[i][k-1],mn[i+(1<<k-1)][k-1]), mx[i][k] = max(mx[i][k-1],mx[i+(1<<k-1)][k-1]);
| ~^~
servers.cpp:14:127: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
14 | for(int i=0;i+(1<<k)-1<n;i++) mn[i][k] = min(mn[i][k-1],mn[i+(1<<k-1)][k-1]), mx[i][k] = max(mx[i][k-1],mx[i+(1<<k-1)][k-1]);
| ~^~
servers.cpp: In function 'void solve()':
servers.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | for(auto [c,a,b] : qs){
| ^
servers.cpp:77:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int md = l + r >> 1;
| ~~^~~
servers.cpp:83:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int md = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
2256 KB |
Output is correct |
| 2 |
Correct |
175 ms |
78216 KB |
Output is correct |
| 3 |
Correct |
175 ms |
78292 KB |
Output is correct |
| 4 |
Correct |
182 ms |
78268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
2256 KB |
Output is correct |
| 2 |
Correct |
175 ms |
78216 KB |
Output is correct |
| 3 |
Correct |
175 ms |
78292 KB |
Output is correct |
| 4 |
Correct |
182 ms |
78268 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
2152 KB |
Extra information in the output file |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2256 KB |
Output is correct |
| 2 |
Correct |
176 ms |
78192 KB |
Output is correct |
| 3 |
Correct |
179 ms |
78216 KB |
Output is correct |
| 4 |
Correct |
218 ms |
78184 KB |
Output is correct |
| 5 |
Incorrect |
22 ms |
2256 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2256 KB |
Output is correct |
| 2 |
Correct |
176 ms |
78192 KB |
Output is correct |
| 3 |
Correct |
179 ms |
78216 KB |
Output is correct |
| 4 |
Correct |
218 ms |
78184 KB |
Output is correct |
| 5 |
Incorrect |
22 ms |
2256 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
