oj.uz

Submission #1102072

# Submission time Handle Problem Language Result Execution time Memory
1102072 2024-10-17T11:34:51 Z Requiem Street Lamps (APIO19_street_lamps) C++17
60 / 100
 737 ms 184780 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "streetlamp"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Street lamp:

Có n trạm dừng kết nối n + 1 cái stop.
ta biết trạng thái của cái stop

Ta có q truy vấn:
- query a b: Từ 1 đến i, ta, tổng các thời điểm mà ta có thể đi từ a b
- toggle i: lật ngược vị trí i

subtask 1: n <= 100, q <= 100. Chạy n * q^2.

subtask 2: b = a + 1.
Tức là ta chỉ quan tâm vị trí i được bật bao nhiêu lần.
cái này bỏ vào prefix sum.

subtask 3: Khi bật nút i, nó sẽ luôn bật.
Nó là bài toán dsu điển hình, tức là 2 đỉnh sẽ không bao giờ bị disconnect.

subtask 4:
Ta toggle trước xong mới đến các truy vấn.
Giả sử ta dsu rollback, khi ta thêm 1 cạnh vào, nó
sẽ liên kết các tplt bên trong đó.

Giả sử nó nối đoạn [1...3] với [4..5] thì ta thêm hình chữ nhật [1...3], [4...5]
với trọng số là thời gian t.

Khi này ta sẽ tính offline bằng sweepline. Giả sử ta cần truy vấn a, b: thì ta chỉ cần truy vấn đoạn [a, b].
Ta có n log n sự kiện thì có tối đa n log n hình chữ nhật,

subtask 5:
Bây giờ ta cần phải xử lý online. Làm thế nào cơ chứ.
Nếu ta cắm BIT2D vào thì nó cũng vẫn sẽ là N log ^ 3 N.
Ta chia các hcn thành 2 loại:
- Đã kết thúc
- Còn thời gian.
**/

const int MAXN = 3e5 + 9;
int n, q, u, v;
char lamp[MAXN];

struct query{
    string type;
    int l, r, u;
} Query[MAXN];

struct DSU{
    struct DSUnode{
        int par;
        int sz;
        int mn;
        int mx;
    };
    vector<DSUnode> D;
    vector<array<int, 6>> changes;
    int small_to_large, path_compression, roll_back;
    DSU(int sz = 0, int _small_to_large = 1, int _path_compression = 1, int _roll_back = 0){
        D.resize(sz + 9);
        small_to_large = _small_to_large;
        path_compression = _path_compression;
        roll_back = _roll_back;
        FOR(i, 0, D.size() - 1){
            D[i].par = i;
            D[i].sz = 1;
            D[i].mn = D[i].mx = i;
        }
    }

    void rollback(){
        if (changes.size() == 0) return;
        array<int, 6> tp = changes.back();
        int u = tp[0];
        int v = tp[1];
        D[u].sz -= D[v].sz;
        D[v].par = v;
        D[u].mn = tp[2], D[u].mx = tp[3];
        D[v].mn = tp[4], D[v].mx = tp[5];
        changes.pop_back();
    }
    int root(int u){
        if (D[u].par == u) return u;
        else {
            int p = root(D[u].par);
            if (path_compression) D[u].par = p;
            return p;
        }
    }

    bool unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (small_to_large and D[u].sz < D[v].sz) swap(u, v);
            D[u].sz += D[v].sz;
            D[v].par = u;
            if (roll_back) changes.pb({u, v, D[u].mn, D[u].mx, D[v].mn, D[v].mx});;

            D[u].mx = max(D[u].mx, D[v].mx);
            D[u].mn = min(D[u].mn, D[v].mn);
            return true;
        }
        return false;
    }
};
namespace subtask1{
    bool check(){
        return n <= 100 and q <= 100;
    }


    DSU timelineDSU[103];
    void solve(){
        FOR(i, 1, q){
            timelineDSU[i] = DSU(n + 1);
            FOR(j, 1, n){
                if (lamp[j] == '1') {
                    timelineDSU[i].unite(j, j + 1);
                }
            }

            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                lamp[u] = ((lamp[u] == '0') ? '1' : '0');
            }
            else{
                int ans = 0;
                FOR(j, 1, i){
                    if (timelineDSU[j].root(Query[i].l) == timelineDSU[j].root(Query[i].r)) {
                        ans++;
                    }
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask2{
    bool check(){
        FOR(i, 1, q){
            if (Query[i].type == "query" and Query[i].l != Query[i].r - 1) return false;
        }
        return true;
    }

    int pre[300003], lastTime[MAXN];
    void solve(){
        FOR(i, 1, n){
            pre[i] = 0;
            if (lamp[i] == '1') lastTime[i] = 1;
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                if (lamp[u] == '1') {
                    pre[u] += i - lastTime[u] + 1;
                    lastTime[u] = 0;
                    lamp[u] = '0';
                }
                else{
                    lastTime[u] = i + 1;
                    lamp[u] = '1';
                }
            }
            if (Query[i].type == "query"){
                int ans = pre[Query[i].l];
                if (lamp[Query[i].l] == '1'){
                    ans += i - lastTime[Query[i].l] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask3{
    char tmp[300005];
    bool check(){
        FOR(i, 1, n){
            tmp[i] = lamp[i];
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and tmp[Query[i].u] == '1') return false;
            if (Query[i].type == "toggle") tmp[Query[i].u] = '1';
        }
        return true;
    }

    /**
    Voi 2 dinh a va b, ta can tim thoi gian dau tien ma hai thang do ket hop lam 1. Cái này có thể giải bằng
    chặt nhị phân song song.

    Dùng reachability Tree.
    **/

    vector<int> reachability[MAXN * 2];
    int edgeTime[MAXN * 2];

    int P[22][MAXN * 2], depth[MAXN * 2];

    void dfs(int u, int p){
        P[0][u] = p;
        for(auto v: reachability[u]){
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int lca(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
            if (P[i][u] != -1 and depth[P[i][u]] >= depth[v]) u = P[i][u];
        }

        if (u == v) return u;

        FORD(i, 20, 0){
            if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]) {
                u = P[i][u];
                v = P[i][v];
            }
        }

        return P[0][u];
    }

    void solve(){
        int small_to_large = 0;
        int path_compression = 1;
        int roll_back = 0;
        DSU D(2 * n + 9, small_to_large, path_compression, roll_back);
        int cntEdge = n + 1;
        FOR(i, 1, n){
            if (lamp[i] == '1') {
                ++cntEdge;
                edgeTime[cntEdge] = 1;

                int r1 = D.root(i);
                int r2 = D.root(i + 1);

                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;
                    reachability[cntEdge].pb(r2);
                }

            }

        }


        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                ++cntEdge;
                edgeTime[cntEdge] = i + 1;
                int r1 = D.root(u);
                int r2 = D.root(u + 1);
                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;

                    reachability[cntEdge].pb(r2);
                }
            }
        }

        FORD(i, 2 * n + 3, 1){
            if (P[0][i] == 0) dfs(i, -1);
        }

        FOR(i, 1, 20){
            FOR(j, 1, 2 * n + 3){
                if (P[i - 1][j] == -1) P[i][j] = -1;
                P[i][j] = P[i - 1][P[i - 1][j]];
            }
        }

        FOR(i, 1, q){
            int ans = 0;
            if (Query[i].type == "query"){
                int l = Query[i].l;
                int r = Query[i].r;
                if (D.root(l) == D.root(r)){
                    int acs = lca(l, r);
                    if (i >= edgeTime[acs]) ans += i - edgeTime[acs] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> q;
    FOR(i, 1, n){
        cin >> lamp[i];
    }
    FOR(i, 1, q){
        cin >> Query[i].type;
        if (Query[i].type == "toggle"){
            cin >> Query[i].u;

        }
        else if (Query[i].type == "query"){
            cin >> Query[i].l >> Query[i].r;
        }
    }

    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

street_lamps.cpp: In constructor 'DSU::DSU(long long int, long long int, long long int, long long int)':
street_lamps.cpp:9:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<DSU::DSUnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
   83 |         FOR(i, 0, D.size() - 1){
      |             ~~~~~~~~~~~~~~~~~~   
street_lamps.cpp:83:9: note: in expansion of macro 'FOR'
   83 |         FOR(i, 0, D.size() - 1){
      |         ^~~
street_lamps.cpp: At global scope:
street_lamps.cpp:322:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  322 | main()
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:326:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  326 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:327:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  327 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33616 KB Output is correct
2 Correct 6 ms 33616 KB Output is correct
3 Correct 6 ms 33616 KB Output is correct
4 Correct 7 ms 33872 KB Output is correct
5 Correct 7 ms 33884 KB Output is correct
6 Correct 6 ms 33872 KB Output is correct
7 Correct 9 ms 33872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 36424 KB Output is correct
2 Correct 59 ms 36492 KB Output is correct
3 Correct 63 ms 36624 KB Output is correct
4 Correct 77 ms 38728 KB Output is correct
5 Correct 70 ms 38992 KB Output is correct
6 Correct 62 ms 38472 KB Output is correct
7 Correct 72 ms 36424 KB Output is correct
8 Correct 85 ms 40008 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 76880 KB Output is correct
2 Correct 11 ms 76880 KB Output is correct
3 Correct 11 ms 76880 KB Output is correct
4 Correct 11 ms 76880 KB Output is correct
5 Correct 209 ms 168964 KB Output is correct
6 Correct 270 ms 173900 KB Output is correct
7 Correct 366 ms 174420 KB Output is correct
8 Correct 660 ms 184652 KB Output is correct
9 Correct 83 ms 80376 KB Output is correct
10 Correct 98 ms 80716 KB Output is correct
11 Correct 102 ms 80784 KB Output is correct
12 Correct 122 ms 159384 KB Output is correct
13 Correct 737 ms 184780 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33616 KB Output is correct
2 Correct 6 ms 33616 KB Output is correct
3 Correct 6 ms 33616 KB Output is correct
4 Correct 7 ms 33872 KB Output is correct
5 Correct 7 ms 33884 KB Output is correct
6 Correct 6 ms 33872 KB Output is correct
7 Correct 9 ms 33872 KB Output is correct
8 Correct 57 ms 36424 KB Output is correct
9 Correct 59 ms 36492 KB Output is correct
10 Correct 63 ms 36624 KB Output is correct
11 Correct 77 ms 38728 KB Output is correct
12 Correct 70 ms 38992 KB Output is correct
13 Correct 62 ms 38472 KB Output is correct
14 Correct 72 ms 36424 KB Output is correct
15 Correct 85 ms 40008 KB Output is correct
16 Correct 11 ms 76880 KB Output is correct
17 Correct 11 ms 76880 KB Output is correct
18 Correct 11 ms 76880 KB Output is correct
19 Correct 11 ms 76880 KB Output is correct
20 Correct 209 ms 168964 KB Output is correct
21 Correct 270 ms 173900 KB Output is correct
22 Correct 366 ms 174420 KB Output is correct
23 Correct 660 ms 184652 KB Output is correct
24 Correct 83 ms 80376 KB Output is correct
25 Correct 98 ms 80716 KB Output is correct
26 Correct 102 ms 80784 KB Output is correct
27 Correct 122 ms 159384 KB Output is correct
28 Correct 737 ms 184780 KB Output is correct
29 Incorrect 7 ms 33616 KB Output isn't correct
30 Halted 0 ms 0 KB -