oj.uz

Submission #683272

# Submission time Handle Problem Language Result Execution time Memory
683272 2023-01-18T05:32:04 Z Nursik Street Lamps (APIO19_street_lamps) C++14
40 / 100
 166 ms 71000 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);
            }
            else{
                upd(x[i], i);
            }
        }
        exit(0);
    }
}
/*
 */

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 62936 KB Output is correct
2 Correct 38 ms 62948 KB Output is correct
3 Correct 40 ms 62900 KB Output is correct
4 Correct 35 ms 62984 KB Output is correct
5 Correct 31 ms 63060 KB Output is correct
6 Correct 31 ms 62880 KB Output is correct
7 Correct 31 ms 62940 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 68280 KB Output is correct
2 Correct 118 ms 68204 KB Output is correct
3 Correct 114 ms 68184 KB Output is correct
4 Correct 142 ms 71000 KB Output is correct
5 Correct 123 ms 70280 KB Output is correct
6 Correct 117 ms 69192 KB Output is correct
7 Correct 126 ms 68620 KB Output is correct
8 Correct 166 ms 70128 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 62936 KB Output is correct
2 Correct 38 ms 62948 KB Output is correct
3 Correct 40 ms 62900 KB Output is correct
4 Correct 35 ms 62984 KB Output is correct
5 Correct 31 ms 63060 KB Output is correct
6 Correct 31 ms 62880 KB Output is correct
7 Correct 31 ms 62940 KB Output is correct
8 Correct 104 ms 68280 KB Output is correct
9 Correct 118 ms 68204 KB Output is correct
10 Correct 114 ms 68184 KB Output is correct
11 Correct 142 ms 71000 KB Output is correct
12 Correct 123 ms 70280 KB Output is correct
13 Correct 117 ms 69192 KB Output is correct
14 Correct 126 ms 68620 KB Output is correct
15 Correct 166 ms 70128 KB Output is correct
16 Incorrect 31 ms 62992 KB Output isn't correct
17 Halted 0 ms 0 KB -