oj.uz

Submission #683277

# Submission time Handle Problem Language Result Execution time Memory
683277 2023-01-18T05:46:43 Z Nursik Street Lamps (APIO19_street_lamps) C++14
60 / 100
 295 ms 78036 KB 
#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
#define bug cout << "bug\n";

const ll maxn = 1e6 + 1, maxm = 2e2 + 1;
const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 126067, base = 1000050017,
         biginf = 5e18;
const ld eps = 1e-15;
using namespace std;

int subtask1 = 1;
int subtask2 = 1;
int subtask3 = 1;
int n, q;
string kek;
string s[maxn], query[maxn];
int l[maxn], r[maxn], x[maxn], t[maxn * 4];
int last[maxn], answ[maxn];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
    if (tl == tr){
        t[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        upd(pos, val, v + v, tl, tm);
    else
        upd(pos, val, v + v + 1, tm + 1, tr);
    t[v] = max(t[v + v], t[v + v + 1]);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n){
    if (l <= tl && tr <= r){
        return t[v];
    }
    if (l > tr || r < tl)
        return -inf;
    int tm = (tl + tr) / 2;
    return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    cin >> s[0];
    kek = s[0];
    for (int i = 1; i <= q; ++i){
        cin >> query[i];
        if (query[i] == "query"){
            cin >> l[i] >> r[i];
            subtask2 &= (r[i] - l[i] == 1);
        }
        else{
            cin >> x[i];
            if (kek[x[i] - 1] == '1'){
                subtask3 = 0;
            }
            else{
                kek[x[i] - 1] = '1';
            }
        }
    }
    subtask1 &= (n <= 100 && q <= 100);
    if (subtask1){
    s[1] = s[0];
    for (int i = 1; i <= q; ++i){
       // cout << i << " " << s[i] << '\n';
        if (query[i] == "query"){
            int ans = 0;
            for (int j = i; j >= 1; --j){
                int ok = 1;
                for (int k = l[i]; k <= r[i] - 1; ++k){
                    ok &= (s[j][k - 1] == '1');
                }
                if (ok){
                    ans += 1;
                }
            }
            cout << ans << '\n';
            s[i + 1] = s[i];
        }
        else{
            s[i + 1] = s[i];
            if (s[i + 1][x[i] - 1] == '1'){
                s[i + 1][x[i] - 1] = '0';
            }
            else{
                s[i + 1][x[i] - 1] = '1';
            }
        }
    }
    exit(0);
    }
    if (subtask2){
        for (int i = 0; i < n; ++i){
            last[i] = -1;
            if (s[0][i] == '1'){
                last[i] = 0;
            }
        }
        for (int i = 1; i <= q; ++i){
            if (query[i] == "query"){
                if (s[0][l[i] - 1] == '0'){
                    cout << answ[l[i] - 1] << '\n';
                }
                else{
                    cout << answ[l[i] - 1] + i - last[l[i] - 1] << '\n';
                }
            }
            else{
                if (s[0][x[i] - 1] == '0'){
                    last[x[i] - 1] = i;
                    s[0][x[i] - 1] = '1';
                }
                else{
                    answ[x[i] - 1] += i - last[x[i] - 1];
                    s[0][x[i] - 1] = '0';
                }
            }
        }
        exit(0);
    }
    if (subtask3){
        for (int i = 0; i < n; ++i){
            if (s[0][i] == '1'){
                upd(i + 1, 0);
            }
            else{
                upd(i + 1, inf);
            }
        }
        for (int i = 1; i <= q; ++i){
            if (query[i] == "query"){
                int z = get(l[i], r[i] - 1);
                cout << max(0, i - z) << '\n';;
            }
            else{
                upd(x[i], i);
            }
        }
        exit(0);
    }
}
/*
 */

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62932 KB Output is correct
2 Correct 28 ms 62932 KB Output is correct
3 Correct 29 ms 62952 KB Output is correct
4 Correct 29 ms 62844 KB Output is correct
5 Correct 33 ms 62948 KB Output is correct
6 Correct 30 ms 62892 KB Output is correct
7 Correct 29 ms 62944 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 67896 KB Output is correct
2 Correct 109 ms 67940 KB Output is correct
3 Correct 108 ms 68004 KB Output is correct
4 Correct 115 ms 70728 KB Output is correct
5 Correct 114 ms 69864 KB Output is correct
6 Correct 116 ms 68756 KB Output is correct
7 Correct 147 ms 68320 KB Output is correct
8 Correct 125 ms 69724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62912 KB Output is correct
2 Correct 35 ms 62976 KB Output is correct
3 Correct 30 ms 62932 KB Output is correct
4 Correct 32 ms 62900 KB Output is correct
5 Correct 170 ms 75572 KB Output is correct
6 Correct 207 ms 76228 KB Output is correct
7 Correct 278 ms 76832 KB Output is correct
8 Correct 295 ms 77996 KB Output is correct
9 Correct 118 ms 68792 KB Output is correct
10 Correct 153 ms 69252 KB Output is correct
11 Correct 126 ms 69280 KB Output is correct
12 Correct 291 ms 76624 KB Output is correct
13 Correct 264 ms 78036 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62932 KB Output is correct
2 Correct 28 ms 62932 KB Output is correct
3 Correct 29 ms 62952 KB Output is correct
4 Correct 29 ms 62844 KB Output is correct
5 Correct 33 ms 62948 KB Output is correct
6 Correct 30 ms 62892 KB Output is correct
7 Correct 29 ms 62944 KB Output is correct
8 Correct 105 ms 67896 KB Output is correct
9 Correct 109 ms 67940 KB Output is correct
10 Correct 108 ms 68004 KB Output is correct
11 Correct 115 ms 70728 KB Output is correct
12 Correct 114 ms 69864 KB Output is correct
13 Correct 116 ms 68756 KB Output is correct
14 Correct 147 ms 68320 KB Output is correct
15 Correct 125 ms 69724 KB Output is correct
16 Correct 29 ms 62912 KB Output is correct
17 Correct 35 ms 62976 KB Output is correct
18 Correct 30 ms 62932 KB Output is correct
19 Correct 32 ms 62900 KB Output is correct
20 Correct 170 ms 75572 KB Output is correct
21 Correct 207 ms 76228 KB Output is correct
22 Correct 278 ms 76832 KB Output is correct
23 Correct 295 ms 77996 KB Output is correct
24 Correct 118 ms 68792 KB Output is correct
25 Correct 153 ms 69252 KB Output is correct
26 Correct 126 ms 69280 KB Output is correct
27 Correct 291 ms 76624 KB Output is correct
28 Correct 264 ms 78036 KB Output is correct
29 Incorrect 28 ms 62888 KB Output isn't correct
30 Halted 0 ms 0 KB -