oj.uz

Submission #447479

# Submission time Handle Problem Language Result Execution time Memory
447479 2021-07-26T13:52:41 Z K4YAN Street Lamps (APIO19_street_lamps) C++17
40 / 100
 687 ms 30528 KB 
//Be Name Khoda
// 06:10 - 13:15

#include<bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")

using namespace std;

typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define plll pair<pll, ll>
#define piii pair<pii, int>
#define piiii pair<pii, pii>

const int mxn = 3e5 + 16;
int n, q, v, u;
string s, h, cur;
vector<piii> qu;
vector<int> change[mxn];
int last[mxn];
bool mark[mxn];

void input() {

    cin >> n >> q;
    cin >> s;
    cur = s;
    for(int i = 0; i < q; i++) {
        cin >> h;
        if(h == "query") {
            cin >> v >> u;
            v--, u--;
            qu.push_back({{1, v}, u});
        }
        else {
            cin >> v;
            v--;
            qu.push_back({{2, v}, v});
        }
    }

}

void solve() {

    if(q <= 100 && n <= 100) {
        for(int i = 0; i < qu.size(); i++) {
            if(qu[i].first.first == 1) {
                int cnt = 0;
                cur = s;
                v = qu[i].first.second, u = qu[i].second;
                for(int j = 0; j <= i; j++) {
                    bool b = true;
                    for(int w = v; w < u; w++) {
                        if(cur[w] == '0') {
                            b = false;
                            break;
                        }
                    }
                    if(b) {
                        cnt++;
                    }
                    if(qu[j].first.first == 2) {
                        if(cur[qu[j].second] == '1') cur[qu[j].second] = '0';
                        else {
                            cur[qu[j].second] = '1';
                        }
                    }
                }
                cout << cnt << endl;
            }
        }
        return;
    }
    for(int i = 0; i < n; i++) {
        change[i].push_back(0);
        if(s[i] == '1') {
            mark[i] = 1;
            last[i] = 1;
        }
        else {
            mark[i] = 0;
        }
    }
    for(int i = 0; i < qu.size(); i++) {
        if(qu[i].first.first == 1) {
            v = qu[i].first.second;
            if(mark[v]) {
                last[v] += (i - change[v].back());
            }
            change[v].push_back(i);
            cout << last[v] << endl;
        }
        else {
            v = qu[i].first.second;
            if(!mark[v]) {
                mark[v] = 1;
                change[v].push_back(i);
            }
            else {
                mark[v] = 0;
                last[v] += (i - change[v].back());
                change[v].push_back(i);
            }
        }
    }


}

int main() {

    ios_base::sync_with_stdio(false);

    input(), solve();

    return 0;

}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message

street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0; i < qu.size(); i++) {
      |                        ~~^~~~~~~~~~~
street_lamps.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < qu.size(); i++) {
      |                    ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7368 KB Output is correct
5 Correct 5 ms 7368 KB Output is correct
6 Correct 5 ms 7288 KB Output is correct
7 Correct 5 ms 7368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 13684 KB Output is correct
2 Correct 332 ms 17216 KB Output is correct
3 Correct 333 ms 17844 KB Output is correct
4 Correct 439 ms 28352 KB Output is correct
5 Correct 479 ms 28732 KB Output is correct
6 Correct 388 ms 28228 KB Output is correct
7 Correct 685 ms 27980 KB Output is correct
8 Correct 687 ms 30528 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7368 KB Output is correct
5 Correct 5 ms 7368 KB Output is correct
6 Correct 5 ms 7288 KB Output is correct
7 Correct 5 ms 7368 KB Output is correct
8 Correct 317 ms 13684 KB Output is correct
9 Correct 332 ms 17216 KB Output is correct
10 Correct 333 ms 17844 KB Output is correct
11 Correct 439 ms 28352 KB Output is correct
12 Correct 479 ms 28732 KB Output is correct
13 Correct 388 ms 28228 KB Output is correct
14 Correct 685 ms 27980 KB Output is correct
15 Correct 687 ms 30528 KB Output is correct
16 Incorrect 4 ms 7372 KB Output isn't correct
17 Halted 0 ms 0 KB -