oj.uz

Submission #163978

# Submission time Handle Problem Language Result Execution time Memory
163978 2019-11-16T13:37:26 Z Leonardo_Paes Street Lamps (APIO19_street_lamps) C++17
40 / 100
 242 ms 30968 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-1, meio, ans = t-1;

                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 18 ms 16760 KB Output is correct
2 Correct 17 ms 16760 KB Output is correct
3 Correct 19 ms 16760 KB Output is correct
4 Correct 19 ms 16764 KB Output is correct
5 Correct 17 ms 16764 KB Output is correct
6 Correct 17 ms 16760 KB Output is correct
7 Correct 18 ms 16760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 20956 KB Output is correct
2 Correct 142 ms 21040 KB Output is correct
3 Correct 126 ms 21248 KB Output is correct
4 Correct 217 ms 26844 KB Output is correct
5 Correct 228 ms 29944 KB Output is correct
6 Correct 209 ms 26336 KB Output is correct
7 Correct 178 ms 20088 KB Output is correct
8 Correct 242 ms 30968 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 16760 KB Output isn't correct
2 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 19 ms 16760 KB Output is correct
4 Correct 19 ms 16764 KB Output is correct
5 Correct 17 ms 16764 KB Output is correct
6 Correct 17 ms 16760 KB Output is correct
7 Correct 18 ms 16760 KB Output is correct
8 Correct 186 ms 20956 KB Output is correct
9 Correct 142 ms 21040 KB Output is correct
10 Correct 126 ms 21248 KB Output is correct
11 Correct 217 ms 26844 KB Output is correct
12 Correct 228 ms 29944 KB Output is correct
13 Correct 209 ms 26336 KB Output is correct
14 Correct 178 ms 20088 KB Output is correct
15 Correct 242 ms 30968 KB Output is correct
16 Incorrect 18 ms 16764 KB Output isn't correct
17 Halted 0 ms 0 KB -