oj.uz

Submission #983223

# Submission time Handle Problem Language Result Execution time Memory
983223 2024-05-15T09:35:37 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 74 ms 25436 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;
    }
    cout << 1 / 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '0')
            up(1, n, i + 1, 1e9, 1);
    }
    for(int i = 1; i <= tt; i++){
        if(type[i][0] == 'q'){
            cout << max(0, i - get_mx(1, n, l[i], r[i] - 1, 1)) << "\n";
        }
        else{
            up(1, n, i, l[i], 1);
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:111:15: warning: division by zero [-Wdiv-by-zero]
  111 |     cout << 1 / 0;
      |             ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12720 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 10588 KB Output is correct
7 Correct 3 ms 12772 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15696 KB Output is correct
2 Correct 51 ms 13520 KB Output is correct
3 Correct 51 ms 13652 KB Output is correct
4 Correct 59 ms 17808 KB Output is correct
5 Correct 59 ms 18160 KB Output is correct
6 Correct 52 ms 15856 KB Output is correct
7 Correct 71 ms 13796 KB Output is correct
8 Correct 74 ms 15080 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 25436 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 25432 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12720 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 10588 KB Output is correct
7 Correct 3 ms 12772 KB Output is correct
8 Correct 47 ms 15696 KB Output is correct
9 Correct 51 ms 13520 KB Output is correct
10 Correct 51 ms 13652 KB Output is correct
11 Correct 59 ms 17808 KB Output is correct
12 Correct 59 ms 18160 KB Output is correct
13 Correct 52 ms 15856 KB Output is correct
14 Correct 71 ms 13796 KB Output is correct
15 Correct 74 ms 15080 KB Output is correct
16 Runtime error 11 ms 25436 KB Execution killed with signal 4
17 Halted 0 ms 0 KB -