oj.uz

Submission #163976

# Submission time Handle Problem Language Result Execution time Memory
163976 2019-11-16T13:31:52 Z Leonardo_Paes Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 30976 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{
        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 << '\n';

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

Subtask #1
20.0 / 20.0

# 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 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 18 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 186 ms 20984 KB Output is correct
2 Correct 142 ms 20984 KB Output is correct
3 Correct 134 ms 21128 KB Output is correct
4 Correct 208 ms 26728 KB Output is correct
5 Correct 212 ms 29916 KB Output is correct
6 Correct 205 ms 26204 KB Output is correct
7 Correct 170 ms 20088 KB Output is correct
8 Correct 242 ms 30976 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 25 ms 16856 KB Output is correct
3 Correct 35 ms 16868 KB Output is correct
4 Correct 24 ms 16808 KB Output is correct
5 Execution timed out 5087 ms 20632 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# 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 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 18 ms 16760 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct
8 Correct 186 ms 20984 KB Output is correct
9 Correct 142 ms 20984 KB Output is correct
10 Correct 134 ms 21128 KB Output is correct
11 Correct 208 ms 26728 KB Output is correct
12 Correct 212 ms 29916 KB Output is correct
13 Correct 205 ms 26204 KB Output is correct
14 Correct 170 ms 20088 KB Output is correct
15 Correct 242 ms 30976 KB Output is correct
16 Correct 17 ms 16760 KB Output is correct
17 Correct 25 ms 16856 KB Output is correct
18 Correct 35 ms 16868 KB Output is correct
19 Correct 24 ms 16808 KB Output is correct
20 Execution timed out 5087 ms 20632 KB Time limit exceeded
21 Halted 0 ms 0 KB -