oj.uz

Submission #934342

# Submission time Handle Problem Language Result Execution time Memory
934342 2024-02-27T07:47:30 Z haxorman Street Lamps (APIO19_street_lamps) C++14
20 / 100
 240 ms 65984 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 3e5 + 7;

struct Query {
    int a, b, lb, rb, id, pos;
};

int dsu[mxN], arr[mxN], cur[mxN], ans[mxN];
Query que[mxN];
vector<int> check[mxN];

int find(int x) {
    return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) {
        return;
    }

    if (dsu[x] > dsu[y]) {
        swap(x, y);
    }
    dsu[x] += dsu[y];
    dsu[y] = x;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;

        arr[i] = (c == '1');
    }
    
    int idx = 0;
    vector<pair<int,int>> tog;
    for (int i = 0; i < q; ++i) {
        string t;
        cin >> t;

        if (t[0] == 'q') {
            int a, b;
            cin >> a >> b;

            que[idx] = {a, b, 0, (int) tog.size(), idx, i};
            check[tog.size() / 2].push_back(idx);
            ++idx;
        }
        else {
            int ind;
            cin >> ind;

            tog.push_back({ind, i});
        }
    }
    
    int cnt = idx;
    while (cnt) {
        memset(dsu, -1, sizeof(dsu));
        for (int i = 1; i <= n; ++i) {
            if (arr[i]) {
                unite(i, i+1);
            }
        }

        for (int i = 0; i <= tog.size(); ++i) {
            while (check[i].size()) {
                int id = check[i].back();
                check[i].pop_back();

                int a = que[id].a, b = que[id].b, lb = que[id].lb, rb = que[id].rb;
                if (find(a) == find(b)) {
                    rb = i - 1;
                    ans[id] = que[id].pos - (!i ? -1 : tog[i-1].second);
                }
                else {
                    lb = i + 1;
                }
                
                if (rb < lb) {
                    --cnt;
                }
                else {
                    que[id].lb = lb, que[id].rb = rb;
                    check[(lb+rb)/2].push_back(id);
                }
            }

            if (i < tog.size()) {
                unite(tog[i].first, tog[i].first+1);
            }
        }
    }

    for (int i = 0; i < idx; ++i) {
        cout << ans[i] << "\n";
    }
}

Compilation message

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:77:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i <= tog.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
street_lamps.cpp:100:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             if (i < tog.size()) {
      |                 ~~^~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 4 ms 16488 KB Output is correct
3 Correct 4 ms 16540 KB Output is correct
4 Correct 4 ms 16656 KB Output is correct
5 Correct 97 ms 27972 KB Output is correct
6 Correct 186 ms 48292 KB Output is correct
7 Correct 240 ms 65984 KB Output is correct
8 Correct 84 ms 42512 KB Output is correct
9 Correct 64 ms 39928 KB Output is correct
10 Correct 67 ms 43824 KB Output is correct
11 Correct 67 ms 41684 KB Output is correct
12 Correct 82 ms 39420 KB Output is correct
13 Correct 82 ms 41324 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Incorrect 6 ms 16544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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