Submission #163975

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

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 << 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{
        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];

                int ini = 0, fim = toggles.size()-1, 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 << endl;

                toggles.push_back(0);
            }
            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];
                                ^
# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 18 ms 16760 KB Output is correct
3 Correct 18 ms 16760 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 20 ms 16760 KB Output is correct
7 Correct 19 ms 16760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 582 ms 21104 KB Output is correct
2 Correct 672 ms 21064 KB Output is correct
3 Correct 533 ms 21104 KB Output is correct
4 Correct 645 ms 27036 KB Output is correct
5 Correct 703 ms 29944 KB Output is correct
6 Correct 554 ms 26376 KB Output is correct
7 Correct 988 ms 20248 KB Output is correct
8 Correct 1049 ms 31032 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 27 ms 16760 KB Output is correct
3 Correct 34 ms 16888 KB Output is correct
4 Correct 27 ms 16888 KB Output is correct
5 Execution timed out 5085 ms 20688 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 46 ms 16888 KB Output is correct
2 Incorrect 43 ms 16888 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 18 ms 16760 KB Output is correct
3 Correct 18 ms 16760 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 20 ms 16760 KB Output is correct
7 Correct 19 ms 16760 KB Output is correct
8 Correct 582 ms 21104 KB Output is correct
9 Correct 672 ms 21064 KB Output is correct
10 Correct 533 ms 21104 KB Output is correct
11 Correct 645 ms 27036 KB Output is correct
12 Correct 703 ms 29944 KB Output is correct
13 Correct 554 ms 26376 KB Output is correct
14 Correct 988 ms 20248 KB Output is correct
15 Correct 1049 ms 31032 KB Output is correct
16 Correct 17 ms 16760 KB Output is correct
17 Correct 27 ms 16760 KB Output is correct
18 Correct 34 ms 16888 KB Output is correct
19 Correct 27 ms 16888 KB Output is correct
20 Execution timed out 5085 ms 20688 KB Time limit exceeded
21 Halted 0 ms 0 KB -