oj.uz

Submission #721816

# Submission time Handle Problem Language Result Execution time Memory
721816 2023-04-11T07:35:22 Z Darren0724 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 973 ms 45084 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
struct seg{
    seg *lc,*rc;
    int l,r,m;
    int mx=INF;
    seg(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new seg(l,m);
        rc=new seg(m,r);
    }
    void add(int p,int x){
        if(r-l==1){
           mx=x;
           return;
        }
        if(p<m){
            lc->add(p,x);
        }
        else{
            rc->add(p,x);
        }
        mx=max(lc->mx,rc->mx);
    }
    int ask(int a,int b){
        if(a<=l&&b>=r){
            //cout<<mx<<endl;
            return mx;
        }
        int ans=-INF;
        if(a<m){
            ans=max(ans,lc->ask(a,b));
        }
        if(b>m){
            ans=max(ans,rc->ask(a,b));
        }
        return ans;
    }
};
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    vector<int> a(n);
    seg *tr=new seg(0,n);
    for(int i=0;i<n;i++){
        char c;cin>>c;
        a[i]=c-'0'-1;
        if(a[i]==0){
            tr->add(i,0);
        }
    }
    vector<int> ans(n);
    for(int i=1;i<=q;i++){
        string s;cin>>s;
        if(s=="query"){
            int x,y;cin>>x>>y;x--;y--;
            int p=tr->ask(x,y);
            //cout<<p<<endl;
            p=min(p,i);
            cout<<i-p<<endl;
        }
        else{
            int p;cin>>p;p--;
            tr->add(p,i);
        }
    }

    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 286 ms 43268 KB Output is correct
6 Correct 486 ms 43196 KB Output is correct
7 Correct 727 ms 43440 KB Output is correct
8 Correct 973 ms 45084 KB Output is correct
9 Correct 388 ms 1668 KB Output is correct
10 Correct 544 ms 1660 KB Output is correct
11 Correct 406 ms 1776 KB Output is correct
12 Correct 842 ms 43724 KB Output is correct
13 Correct 880 ms 44976 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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