oj.uz

Submission #163982

# Submission time Handle Problem Language Result Execution time Memory
163982 2019-11-16T13:57:58 Z Leonardo_Paes Street Lamps (APIO19_street_lamps) C++17
60 / 100
 1138 ms 35092 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;

int n, q;

string initial;

vector<int> toggles;

vector<int> events[maxn];

string query[maxn];

int aa[maxn], bb[maxn];

bool subtask_1(){
    return n<=100 and q<=100;
}

bool subtask_2(){
    bool ok = true;

    for(int i=1; i<=q; i++){
        if(query[i][0]=='q' and bb[i]-aa[i]!=1) ok = false;
    }

    return ok;
}

int tree[4*maxn];

void build(int node, int l, int r){
    if(l==r){
        if((int)(initial[l]-'0') == 1) tree[node] = 0;
        else tree[node] = 0x3f3f3f3f;
        return;
    }

    int mid = (l+r) >> 1;

    build(2*node, l, mid);
    build(2*node+1, mid+1, r);

    tree[node] = max(tree[2*node], tree[2*node+1]);
}

void update(int node, int l, int r, int pos, int val){
    if(l==r){
        tree[node] = val;
        return;
    }

    int mid = (l+r) >> 1;

    if(pos<=mid) update(2*node, l, mid, pos, val);
    else update(2*node+1, mid+1, r, pos, val);

    tree[node] = max(tree[2*node], tree[2*node+1]);
}

int queryy(int node, int tl, int tr, int l, int r){
    if(tl > r or tr < l) return 0;
    if(tl >= l and tr <= r) return tree[node];

    int mid = (tl+tr) >> 1;

    return max(queryy(2*node, tl, mid, l, r), queryy(2*node+1, mid+1, tr, l, r));
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n >> q;

    initial.resize(n+2);

    for(int i=1; i<=n; i++){
        cin >> initial[i];
        if(initial[i]=='1') events[i].push_back(0);
    }

    for(int i=1; i<=q; i++){
        cin >> query[i];
        if(query[i][0] == 'q') cin >> aa[i] >> bb[i];
        else cin >> aa[i];
    }

    if(subtask_1()){
        toggles.push_back(0);

        for(int t=1; t<=q; t++){
            string op = query[t];

            if(op[0] == 'q'){
                int a = aa[t], b = bb[t];

                string now = initial;

                int ans = 0;

                for(int i=0; i<toggles.size(); i++){
                    if(now[toggles[i]]=='0') now[toggles[i]] = '1';
                    else now[toggles[i]] = '0';

                    bool ok = true;

                    for(int j=a; j<b; j++) if(now[j] == '0') ok = false;

                    if(ok) ans++;
                }

                cout << ans << endl;

                toggles.push_back(0);
            }
            else{
                int i = aa[t];

                toggles.push_back(i);
            }
        }
    }
    else if(subtask_2()){
        for(int t=1; t<=q; t++){
            string op = query[t];

            if(op[0] == 'q'){
                int a = aa[t], b = bb[t];

                int ans = 0;

                for(int i=0; i<events[a].size(); i++){
                    if(i%2){
                        ans += events[a][i] - events[a][i-1];
                    }
                }

                if(events[a].size()%2) ans += t - events[a].back();

                cout << ans << endl;
            }
            else{
                int i = aa[t];

                events[i].push_back(t);
            }
        }
    }
    else{
        build(1, 1, n);

        for(int t=1; t<=q; t++){
            string op = query[t];

            if(op[0] == 'q'){
                int a = aa[t], b = bb[t];

                int ans = queryy(1, 1, n, a, b-1);

                if(ans == 0x3f3f3f3f) cout << 0 << endl;
                else cout << t-ans << endl;
            }
            else{
                int i = aa[t];

                update(1, 1, n, i, t);
            }
        }
    }

    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:104:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<toggles.size(); i++){
                              ~^~~~~~~~~~~~~~~
street_lamps.cpp:135:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<events[a].size(); i++){
                              ~^~~~~~~~~~~~~~~~~
street_lamps.cpp:131:32: warning: unused variable 'b' [-Wunused-variable]
                 int a = aa[t], b = bb[t];
                                ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16760 KB Output is correct
2 Correct 17 ms 16760 KB Output is correct
3 Correct 17 ms 16760 KB Output is correct
4 Correct 17 ms 16760 KB Output is correct
5 Correct 17 ms 16760 KB Output is correct
6 Correct 17 ms 16760 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 21068 KB Output is correct
2 Correct 538 ms 21004 KB Output is correct
3 Correct 531 ms 21244 KB Output is correct
4 Correct 619 ms 26764 KB Output is correct
5 Correct 696 ms 29944 KB Output is correct
6 Correct 520 ms 26300 KB Output is correct
7 Correct 957 ms 20184 KB Output is correct
8 Correct 1031 ms 31060 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 18 ms 16764 KB Output is correct
3 Correct 19 ms 16820 KB Output is correct
4 Correct 20 ms 16760 KB Output is correct
5 Correct 178 ms 23672 KB Output is correct
6 Correct 473 ms 26584 KB Output is correct
7 Correct 761 ms 29700 KB Output is correct
8 Correct 1124 ms 35092 KB Output is correct
9 Correct 838 ms 19832 KB Output is correct
10 Correct 820 ms 19880 KB Output is correct
11 Correct 1022 ms 19908 KB Output is correct
12 Correct 1102 ms 24292 KB Output is correct
13 Correct 1138 ms 35032 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16760 KB Output is correct
2 Correct 17 ms 16760 KB Output is correct
3 Correct 17 ms 16760 KB Output is correct
4 Correct 17 ms 16760 KB Output is correct
5 Correct 17 ms 16760 KB Output is correct
6 Correct 17 ms 16760 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct
8 Correct 581 ms 21068 KB Output is correct
9 Correct 538 ms 21004 KB Output is correct
10 Correct 531 ms 21244 KB Output is correct
11 Correct 619 ms 26764 KB Output is correct
12 Correct 696 ms 29944 KB Output is correct
13 Correct 520 ms 26300 KB Output is correct
14 Correct 957 ms 20184 KB Output is correct
15 Correct 1031 ms 31060 KB Output is correct
16 Correct 17 ms 16760 KB Output is correct
17 Correct 18 ms 16764 KB Output is correct
18 Correct 19 ms 16820 KB Output is correct
19 Correct 20 ms 16760 KB Output is correct
20 Correct 178 ms 23672 KB Output is correct
21 Correct 473 ms 26584 KB Output is correct
22 Correct 761 ms 29700 KB Output is correct
23 Correct 1124 ms 35092 KB Output is correct
24 Correct 838 ms 19832 KB Output is correct
25 Correct 820 ms 19880 KB Output is correct
26 Correct 1022 ms 19908 KB Output is correct
27 Correct 1102 ms 24292 KB Output is correct
28 Correct 1138 ms 35032 KB Output is correct
29 Correct 26 ms 16888 KB Output is correct
30 Incorrect 24 ms 16888 KB Output isn't correct
31 Halted 0 ms 0 KB -