oj.uz

Submission #163980

# Submission time Handle Problem Language Result Execution time Memory
163980 2019-11-16T13:40:33 Z Leonardo_Paes Street Lamps (APIO19_street_lamps) C++17
40 / 100
 251 ms 33884 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;
}

inline bool check(int x, int a, int b){
    string now = initial;

    for(int i=0; i<=x; i++){
        now[toggles[i]] = 1;
    }

    bool ok = true;

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

    return ok;
}

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 << '\n';

                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 << '\n';
            }
            else{
                int i = aa[t];

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

            if(op[0] == 'q'){
                toggles.push_back(0);

                int a = aa[t], b = bb[t];

                int ini = 0, fim = t, meio, ans = t;

                while(ini <= fim){
                    meio = (ini+fim) >> 1;

                    if(check(meio, a, b)){
                        fim = meio - 1;
                        ans = meio;
                    }
                    else{
                        ini = meio + 1;
                    }
                }

                cout << t-ans << '\n';
            }
            else{
                int i = aa[t];

                toggles.push_back(i);
            }
        }
    }

    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:80:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<toggles.size(); i++){
                              ~^~~~~~~~~~~~~~~
street_lamps.cpp:111:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<events[a].size(); i++){
                              ~^~~~~~~~~~~~~~~~~
street_lamps.cpp:107: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 19 ms 16760 KB Output is correct
2 Correct 18 ms 16760 KB Output is correct
3 Correct 19 ms 16760 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 18 ms 16764 KB Output is correct
6 Correct 18 ms 16760 KB Output is correct
7 Correct 21 ms 16760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 20900 KB Output is correct
2 Correct 141 ms 20960 KB Output is correct
3 Correct 127 ms 21188 KB Output is correct
4 Correct 219 ms 26744 KB Output is correct
5 Correct 213 ms 29944 KB Output is correct
6 Correct 203 ms 26344 KB Output is correct
7 Correct 171 ms 20088 KB Output is correct
8 Correct 251 ms 30940 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16764 KB Output is correct
2 Runtime error 42 ms 33884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 33784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16760 KB Output is correct
2 Correct 18 ms 16760 KB Output is correct
3 Correct 19 ms 16760 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 18 ms 16764 KB Output is correct
6 Correct 18 ms 16760 KB Output is correct
7 Correct 21 ms 16760 KB Output is correct
8 Correct 184 ms 20900 KB Output is correct
9 Correct 141 ms 20960 KB Output is correct
10 Correct 127 ms 21188 KB Output is correct
11 Correct 219 ms 26744 KB Output is correct
12 Correct 213 ms 29944 KB Output is correct
13 Correct 203 ms 26344 KB Output is correct
14 Correct 171 ms 20088 KB Output is correct
15 Correct 251 ms 30940 KB Output is correct
16 Correct 19 ms 16764 KB Output is correct
17 Runtime error 42 ms 33884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -