oj.uz

Submission #163979

# Submission time Handle Problem Language Result Execution time Memory
163979 2019-11-16T13:37:55 Z Leonardo_Paes Street Lamps (APIO19_street_lamps) C++17
40 / 100
 261 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;

                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 17 ms 16760 KB Output is correct
3 Correct 18 ms 16760 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16788 KB Output is correct
6 Correct 19 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 188 ms 20964 KB Output is correct
2 Correct 148 ms 20988 KB Output is correct
3 Correct 129 ms 21112 KB Output is correct
4 Correct 229 ms 26744 KB Output is correct
5 Correct 219 ms 29932 KB Output is correct
6 Correct 209 ms 26260 KB Output is correct
7 Correct 185 ms 20216 KB Output is correct
8 Correct 261 ms 30968 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 Incorrect 26 ms 16760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16888 KB Output is correct
2 Incorrect 40 ms 16760 KB Output isn't correct
3 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 17 ms 16760 KB Output is correct
3 Correct 18 ms 16760 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16788 KB Output is correct
6 Correct 19 ms 16760 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct
8 Correct 188 ms 20964 KB Output is correct
9 Correct 148 ms 20988 KB Output is correct
10 Correct 129 ms 21112 KB Output is correct
11 Correct 229 ms 26744 KB Output is correct
12 Correct 219 ms 29932 KB Output is correct
13 Correct 209 ms 26260 KB Output is correct
14 Correct 185 ms 20216 KB Output is correct
15 Correct 261 ms 30968 KB Output is correct
16 Correct 17 ms 16760 KB Output is correct
17 Incorrect 26 ms 16760 KB Output isn't correct
18 Halted 0 ms 0 KB -