Submission #683272

#	Time	Username	Problem	Language	Result	Execution time	Memory
683272		Nursik	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	166 ms	71000 KiB

street_lamps

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20