oj.uz

Submission #267132

# Submission time Handle Problem Language Result Execution time Memory
267132 2020-08-15T21:19:39 Z kimbj0709 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 419 ms 29964 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 300050
vector<int> seg(maxn*8,INT_MAX);
void update(int node,int start,int end,int pos,int val){
    if(start==end){
        assert(start==pos);
        seg[node] = val;
        return;
    }
    int mid = (start+end)/2;
    if(pos<=mid){
        update(node*2+1,start,mid,pos,val);
    }
    else{
        update(node*2+2,mid+1,end,pos,val);
    }
    seg[node] = max(seg[node*2+1],seg[node*2+2]);
}
int query(int node,int start,int end,int rangemin,int rangemax){
    if(start>rangemax||end<rangemin){
        return -1;
    }
    if(start>=rangemin&&end<=rangemax){
        return seg[node];
    }
    int mid = (start+end)/2;
    return max(query(node*2+1,start,mid,rangemin,rangemax),query(node*2+2,mid+1,end,rangemin,rangemax));
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin >> n >> q;
    string input;
    cin >> input;
    vector<int> currpos(maxn,0);
    for(int i=0;i<input.length();i++){
        if(input.at(i)=='1'){
            currpos[i+1] = 1;
            update(0,1,n,i+1,0);
        }
    }
    string input1;
    int input2,input3;
    for(int i=1;i<=q;i++){
        cin >> input1;
        if(input1=="toggle"){
            cin >> input2;
            if(currpos[input2]==1){
                currpos[input2] = 0;
                update(0,1,n,input2,INT_MAX);
            }
            else{
                currpos[input2] = 1;
                update(0,1,n,input2,i);
            }
        }
        else{
            cin >> input2 >> input3;
            input3--;
            int mini = query(0,1,n,input2,input3);
            if(mini==INT_MAX){
                cout << 0 << "\n";
            }
            else{
                cout << i-mini << "\n";
            }
        }
    }
 
}

Compilation message

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<input.length();i++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 25080 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 13 ms 21504 KB Output is correct
2 Correct 13 ms 21504 KB Output is correct
3 Correct 16 ms 21504 KB Output is correct
4 Correct 15 ms 21504 KB Output is correct
5 Correct 243 ms 26252 KB Output is correct
6 Correct 255 ms 26892 KB Output is correct
7 Correct 307 ms 27532 KB Output is correct
8 Correct 419 ms 29872 KB Output is correct
9 Correct 117 ms 25208 KB Output is correct
10 Correct 140 ms 25440 KB Output is correct
11 Correct 126 ms 25724 KB Output is correct
12 Correct 323 ms 28428 KB Output is correct
13 Correct 413 ms 29964 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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