oj.uz

Submission #934378

# Submission time Handle Problem Language Result Execution time Memory
934378 2024-02-27T08:52:50 Z VladaMG98 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 410 ms 5212 KB 
// Problem: C - Street Lamps
// Contest: Virtual Judge - 2024-02-27 APIO Simulation
// URL: https://vjudge.net/contest/612540#problem/C
// Memory Limit: 512 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define what_is(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, q;
void subtask1() {
    string s; cin >> s;
    vector<vector<bool>> history;
    vector<bool> cur(n);
    rep(i, 0, n) cur[i] = (s[i] == '1');
    history.push_back(cur);

    while (q--) {
        string what; cin >> what;
        if (what == "query") {
            int l, r; cin >> l >> r;
            l -= 1; r -= 1;
            int ans = 0;
            for (auto ev : history) {
                int cnt = 0;
                rep(k, l, r) cnt += ev[k];
                if (cnt == r - l) ans += 1;
            }
            cout << ans << endl;
        } else {
            int pos; cin >> pos;
            pos -= 1;
            cur[pos] = !cur[pos];
        }
        history.push_back(cur);
    }
}

void subtask2() {
    string s; cin >> s;
    vector<bool> cur(n);
    rep(i, 0, n) cur[i] = (s[i] == '1');

    vector<int> last_turned_on(n, 0);
    vector<int> ans(n, 0);
    int cur_time = 0;
    while (q--) {
        cur_time += 1;
        string what; cin >> what;
        if (what == "query") {
            int l, r; cin >> l >> r;
            l -= 1; r -= 1;
            assert (l + 1 == r);
            // so we only care about l
            int ret = ans[l] + (cur[l] ? cur_time - last_turned_on[l] : 0);
            cout << ret << endl;
        } else {
            int pos; cin >> pos;
            pos -= 1;
            if (cur[pos]) {
                ans[pos] += (cur_time - last_turned_on[pos]);
                cur[pos] = false;
            } else {
                last_turned_on[pos] = cur_time;
                cur[pos] = true;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> q;
    if (n <= 100 && q <= 100) { subtask1(); return 0; }
    subtask2();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 1512 KB Output is correct
2 Correct 222 ms 1360 KB Output is correct
3 Correct 222 ms 1352 KB Output is correct
4 Correct 240 ms 3676 KB Output is correct
5 Correct 267 ms 4188 KB Output is correct
6 Correct 190 ms 3772 KB Output is correct
7 Correct 402 ms 3792 KB Output is correct
8 Correct 410 ms 5212 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 224 ms 1512 KB Output is correct
9 Correct 222 ms 1360 KB Output is correct
10 Correct 222 ms 1352 KB Output is correct
11 Correct 240 ms 3676 KB Output is correct
12 Correct 267 ms 4188 KB Output is correct
13 Correct 190 ms 3772 KB Output is correct
14 Correct 402 ms 3792 KB Output is correct
15 Correct 410 ms 5212 KB Output is correct
16 Runtime error 1 ms 604 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -