Submission #934322

#	Time	Username	Problem	Language	Result	Execution time	Memory
934322		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	126 ms	45412 KiB

street_lamps

#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].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 (stderr)

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