Submission #863550

#	Time	Username	Problem	Language	Result	Execution time	Memory
863550		HossamHero7	Inside information (BOI21_servers)	C++14	0 / 100	6 ms	3660 KiB

servers

#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;
    while(q--){
        int c,a,b=0;
        cin>>c>>a;
        a --;
        if(c != 'C') cin>>b,b --;
        qs.push_back({c,a,b});
        if(c == 'S') time[a] = 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') 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 = md - a, r = md-1;
                else l = md+1;
            }
            cout<<sz1 + sz2 + 1<<endl;
        }
    }
}
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 (stderr)

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:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [c,a,b] : qs){
      |              ^
servers.cpp:76:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |                 int md = l + r >> 1;
      |                          ~~^~~
servers.cpp:82:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |                 int md = l + r >> 1;
      |                          ~~^~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5