oj.uz

Submission #639541

# Submission time Handle Problem Language Result Execution time Memory
639541 2022-09-10T14:44:15 Z Benmath Inside information (BOI21_servers) C++14
0 / 100
 253 ms 660 KB 
#include <bits/stdc++.h>
 
using namespace std;
int tree1[600001];
void update1(int node,int start,int end,int idx,int val){
if(start==end){
    tree1[node]=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
    update1(2*node,start,mid,idx,val);
}else{
update1(2*node+1,mid+1,end,idx,val);
}
tree1[node]=min(tree1[2*node],tree1[2*node+1]);
}
}
int query1(int node,int start,int end,int l,int r){
if(r<start or end<l){
    return 1;
}
if(l<=start and end<=r){
    return tree1[node];
}
int mid=(start+end)/2;
int p1=query1(2*node,start,mid,l,r);
int p2=query1(2*node+1,mid+1,end,l,r);
return min(p1,p2);
}
int tree2[600001];
void update2(int node,int start,int end,int idx,int val){
if(start==end){
    tree2[node]=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
    update2(2*node,start,mid,idx,val);
}else{
update2(2*node+1,mid+1,end,idx,val);
}
tree2[node]=max(tree2[2*node],tree2[2*node+1]);
}
}
int query2(int node,int start,int end,int l,int r){
if(r<start or end<l){
    return 0;
}
if(l<=start and end<=r){
    return tree2[node];
}
int mid=(start+end)/2;
int p1=query2(2*node,start,mid,l,r);
int p2=query2(2*node+1,mid+1,end,l,r);
return max(p1,p2);
}
int main()
{
    int n,k;
    cin>>n>>k;
    int p[n];
    for(int i=0;i<n;i++){
        p[i]=-1;
        update1(1,0,n-2,i,-1);
        update2(1,0,n-2,i,1e9);
    }
    int brojac=1;
    for(int k1=0;k1<(n+k-1);k1++){
        char l;
        cin>>l;
        if(l=='S'){
            int x,y;
            cin>>x>>y;
            x--;
            y--;
            if(x>y){
                swap(x,y);
            }
            p[x]=brojac;
            if(x==0){
                update1(1,0,n-2,0,0);
                update2(1,0,n-2,0,1);
            }else{
            if(p[x]!=-1 and p[x-1]!=-1){
                if(p[x]<p[x-1]){
                    update2(1,0,n-2,x,1);
                }else{
                //	cout<<x<<endl;
                update1(1,0,n-2,x,0);
               // cout<<query1(1,0,n-2,x,x)<<endl;
                }
            }
            if(x!=(n-2)){
            	if(p[x+1]!=-1 and p[x]!=-1){
            		if(p[x+1]<p[x]){
            			update2(1,0,n-2,x+1,1);
					}else{
						update1(1,0,n-2,x+1,0);
					}
				}
			}
            }
           // cout<<query2(1,0,n-2,2,2)<<endl;
            brojac++;
        }else if(l=='Q'){
        int y,x;
        cin>>y>>x;
        x--;
        y--;
      //  cout<<query1(1,0,n-2,3,3)<<endl;
        if(x<y){
            if(y==(x+1)){
                if(p[x]!=-1){
                    cout<<"yes"<<endl;
                }else{
                cout<<"no"<<endl;
                }
            }else{
            int ro=query1(1,0,n-2,x+1,y-1);
            if(ro==0){
                cout<<"yes"<<endl;
            }else{
            cout<<"no"<<endl;
            }
            }
        }else if(x==y){
        cout<<"yes"<<endl;
        }else{
        if(y==(x-1)){
            if(p[x-1]!=-1){
                cout<<"yes"<<endl;
            }else{
            cout<<"no"<<endl;
            }
        }else{
        int ro=query2(1,0,n-2,y+1,x-1);
        //cout<<ro<<endl;
        if(ro==1){
            cout<<"yes"<<endl;
        }else{
        cout<<"no"<<endl;
        }
        }
        }
 
 
        }else{
        int x;
        cin>>x;
        x--;
        int ans1=x;
        int l=x+1;
        int r=n-1;
        while(l<=r){
            int y=l+(r-l)/2;
             if(y==(x+1)){
                if(p[x]!=-1){
                  ans1=max(ans1,y);
                  l=y+1;
                }else{
              r=y-1;
                }
            }else{
            int ro=query1(1,0,n-2,x+1,y-1);
            if(ro==0){
               ans1=max(ans1,y);
               l=y+1;
            }else{
           r=y-1;
            }
            }
        }
        int ans2=x;
        l=0;
        r=x-1;
 
        while(l<=r){
            int y=l+(r-l)/2;
            if(y==(x-1)){
            if(p[x-1]!=-1){
               ans2=min(ans2,y);
               r=y-1;
            }else{
           l=y+1;
            }
        }else{
        int ro=query2(1,0,n-2,y+1,x-1);
        if(ro==1){
         ans2=min(ans2,y);
         r=y-1;
        }else{
       l=y+1;
        }
        }
        }
//cout<<ans2<<endl;
        cout<<ans1-ans2+1<<endl;
        }
    }
 
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 660 KB Output isn't correct
2 Halted 0 ms 0 KB -