oj.uz

Submission #934390

# Submission time Handle Problem Language Result Execution time Memory
934390 2024-02-27T09:22:11 Z VladaMG98 Street Lamps (APIO19_street_lamps) C++17
60 / 100
 449 ms 22968 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;

const int MAXQ = 300010;
int n, q; string s;
int type[MAXQ], a[MAXQ], b[MAXQ];

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

    rep (qq, 1, q + 1) {
        if (type[qq]) {
            int l = a[qq], r = b[qq];
            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 = a[qq];
            pos -= 1;
            cur[pos] = !cur[pos];
        }
        history.push_back(cur);
    }
}

void subtask2() {
    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;
    rep (qq, 1, q + 1) {
        cur_time += 1;
        if (type[qq]) {
            int l = a[qq], r = b[qq];
            l -= 1; r -= 1;
            // 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 = a[qq];
            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 t[MAXQ << 1];
void build() {
    for (int i = n - 1; i > 0; --i) t[i] = max(t[i << 1], t[i << 1 | 1]);
}
void modify (int pos, int val) {
    for (t[pos += n] = val; pos > 1; pos >>= 1) t[pos >> 1] = max(t[pos], t[pos ^ 1]);
}
int query (int l, int r) {
    int ans = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans = max(ans, t[l++]);
        if (r & 1) ans = max(ans, t[--r]);
    }
    return ans;
}
void subtask3() {
    for (int i = 0; i < n; i++) t[n + i] = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') t[n + i] = 0;
    }

    build();
    int cur_time = 0;
    rep (qq, 1, q + 1) {
        cur_time += 1;
        if (type[qq]) {
            int l = a[qq] - 1, r = b[qq] - 1;
            int goes_on = query(l, r);
            if (goes_on >= cur_time) cout << 0 << endl;
            else cout << cur_time - goes_on << endl;
        } else {
            int pos = a[qq] - 1;
            modify(pos, cur_time);
        }
    }
}

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

    cin >> n >> q >> s;
    for (int i = 1; i <= q; i++) {
        string str; cin >> str;
        type[i] = (str == "query");
        if (type[i]) cin >> a[i] >> b[i];
        else cin >> a[i];
}

    if (n <= 100 && q <= 100) { subtask1(); return 0; }
    bool is_two = true;
    for (int i = 1; i <= q; i++) {
        if (type[i] && b[i] != a[i] + 1) {
            is_two = false;
            break;
        }
    }
    if (is_two) { subtask2(); return 0; }

    unordered_map<int, int> toggles;
    for (int i = 1; i <= q; i++) {
        if (!type[i]) toggles[a[i] - 1] += 1;
    }

    bool is_three = true;
    for (auto [k, v] : toggles) {
        if (v > 1) { is_three = false; break; }
        if (s[k] == '1') { is_three = false; break; }
    }

    if (is_three) { subtask3(); return 0; }
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 7764 KB Output is correct
2 Correct 214 ms 8016 KB Output is correct
3 Correct 228 ms 8212 KB Output is correct
4 Correct 233 ms 11808 KB Output is correct
5 Correct 256 ms 12204 KB Output is correct
6 Correct 189 ms 11656 KB Output is correct
7 Correct 393 ms 12264 KB Output is correct
8 Correct 409 ms 13768 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 82 ms 22968 KB Output is correct
6 Correct 203 ms 21196 KB Output is correct
7 Correct 336 ms 17276 KB Output is correct
8 Correct 444 ms 14492 KB Output is correct
9 Correct 307 ms 7192 KB Output is correct
10 Correct 345 ms 7548 KB Output is correct
11 Correct 344 ms 7760 KB Output is correct
12 Correct 445 ms 13412 KB Output is correct
13 Correct 449 ms 14704 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 212 ms 7764 KB Output is correct
9 Correct 214 ms 8016 KB Output is correct
10 Correct 228 ms 8212 KB Output is correct
11 Correct 233 ms 11808 KB Output is correct
12 Correct 256 ms 12204 KB Output is correct
13 Correct 189 ms 11656 KB Output is correct
14 Correct 393 ms 12264 KB Output is correct
15 Correct 409 ms 13768 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 2 ms 2396 KB Output is correct
20 Correct 82 ms 22968 KB Output is correct
21 Correct 203 ms 21196 KB Output is correct
22 Correct 336 ms 17276 KB Output is correct
23 Correct 444 ms 14492 KB Output is correct
24 Correct 307 ms 7192 KB Output is correct
25 Correct 345 ms 7548 KB Output is correct
26 Correct 344 ms 7760 KB Output is correct
27 Correct 445 ms 13412 KB Output is correct
28 Correct 449 ms 14704 KB Output is correct
29 Incorrect 2 ms 2396 KB Output isn't correct
30 Halted 0 ms 0 KB -