oj.uz

답안 #983217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983217 2024-05-15T09:33:32 Z vjudge1 가로등 (APIO19_street_lamps) C++17
40 / 100
 76 ms 23416 KB 
#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>

using namespace std;

int tt = 1, n;
string s;
int k[1001][1001];
int last[300005], kol[300005], l[300005], r[300005];
string type[300005];
int mx[4 * 300005];
void up(int l, int r, int ind, int num, int v){
    if(l > ind || r < ind) return;
    if(l == r){
        mx[v] = num;
        return;
    }
    int mid = (l + r) / 2;
    up(l, mid, ind, num, v * 2);
    up(mid + 1, r, ind, num, v * 2 + 1);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
int get_mx(int l, int r, int l1, int r1, int v){
    if(l > r1 || l1 > r) return 0;
    if(l >= l1 && r1 >= r) return mx[v];
    int mid = (l + r) / 2;
    return max(get_mx(l, mid, l1, r1, v * 2), get_mx(mid + 1, r, l1, r1, v * 2 + 1));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> tt;
    cin >> s;
    if(n <= 100 && tt <= 100){
        while(tt--){
            string ss;
            cin >> ss;
            for(int i = 1; i <= n; i++){
                for(int j = i + 1; j <= n + 1; j++){
                    if(s[j - 2] == '1') k[i][j]++;
                    else break;
                }
            }
            if(ss[0] == 'q'){
                int a, b;
                cin >> a >> b;
                cout << k[a][b] << "\n";
            }
            else{
                int p;
                cin >> p;
                if(s[p - 1] == '0') s[p - 1] = '1';
                else s[p - 1] = '0';

            }
        }
        return 0;
    }
    bool f = 0;
    for(int i = 1; i <= tt; i++){
        cin >> type[i] >> l[i];
        if(type[i][0] == 'q') cin >> r[i];
        if(type[i][0] == 'q' && r[i] - 1 != l[i]) f = 1;
    }
    if(!f){
        for(int i = 1; i <= tt; i++){
            if(type[i][0] == 'q'){
                int num = kol[l[i]];
                if(s[l[i] - 1] == '1') num += (i - last[l[i]]);
                cout << num << "\n";
            }
            else{
                if(s[l[i] - 1] == '1'){
                    kol[l[i]] += (i - last[l[i]]);
                    last[l[i]] = i;
                    s[l[i] - 1] = '0';
                }
                else{
                    last[l[i]] = i;
                    s[l[i] - 1] = '1';
                }
            }
        }
        return 0;
    }
    for(int i = 1; i <= tt; i++){
        if(type[i][0] == 'q'){
            cout << i - get_mx(1, n, l[i], r[i] - 1, 1) << "\n";
        }
        else{
            up(1, n, i, l[i], 1);
        }
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12776 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 10688 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 18768 KB Output is correct
2 Correct 50 ms 16980 KB Output is correct
3 Correct 55 ms 17604 KB Output is correct
4 Correct 60 ms 23008 KB Output is correct
5 Correct 61 ms 23416 KB Output is correct
6 Correct 53 ms 20960 KB Output is correct
7 Correct 68 ms 19688 KB Output is correct
8 Correct 76 ms 20992 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12776 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 10688 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Correct 50 ms 18768 KB Output is correct
9 Correct 50 ms 16980 KB Output is correct
10 Correct 55 ms 17604 KB Output is correct
11 Correct 60 ms 23008 KB Output is correct
12 Correct 61 ms 23416 KB Output is correct
13 Correct 53 ms 20960 KB Output is correct
14 Correct 68 ms 19688 KB Output is correct
15 Correct 76 ms 20992 KB Output is correct
16 Incorrect 3 ms 12632 KB Output isn't correct
17 Halted 0 ms 0 KB -