oj.uz

Submission #885770

# Submission time Handle Problem Language Result Execution time Memory
885770 2023-12-10T16:27:04 Z ByeWorld Synchronization (JOI13_synchronization) C++14
30 / 100
 557 ms 65552 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 1e18;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n, m, q;
vector <int> adj[MAXN];
int a[MAXN], ty[MAXN];
int l[MAXN], r[MAXN];
set <pii> s;

void chmn(int &x, int y){
    x = min(x, y);
}
void chmx(int &x, int y){
    x = max(x, y);
}
struct seg {
    int st[4*MAXN], laz[4*MAXN];
    seg() {
        for(int i=1; i<=4*MAXN-10; i++){
            st[i] = INF; laz[i] = INF;
        }
    }
    void bnc(int id, int l, int r){
        if(laz[id] == INF) return;
        chmn(st[lf], laz[id]); chmn(laz[lf], laz[id]);
        chmn(st[rg], laz[id]); chmn(laz[rg], laz[id]);
        laz[id] = INF;
    }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return INF;
        bnc(id, l, r);
        return min(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
    }
    int upd(int id, int l, int r, int x, int y, int p){
        if(x<=l && r<=y){
            chmn(laz[id], p); chmn(st[id], p);
            return st[id];
        }
        if(r<x || y<l) return st[id];
        bnc(id, l, r);
        return st[id] = min(upd(lf, l, md, x, y, p), upd(rg, md+1, r, x, y, p));
    }
} A; // min - left

struct segtree {
    int st[4*MAXN], laz[4*MAXN];
    segtree() {
        for(int i=1; i<=4*MAXN-10; i++){
            st[i] = -INF; laz[i] = -INF;
        }
    }
    void bnc(int id, int l, int r){
        if(laz[id] == -INF) return;
        chmx(st[lf], laz[id]); chmx(laz[lf], laz[id]);
        chmx(st[rg], laz[id]); chmx(laz[rg], laz[id]);
        laz[id] = -INF;
    }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return -INF;
        bnc(id, l, r);
        return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
    }
    int upd(int id, int l, int r, int x, int y, int p){
        if(x<=l && r<=y){
            chmx(laz[id], p); chmx(st[id], p);
            return st[id];
        }
        if(r<x || y<l) return st[id];
        bnc(id, l, r);
        return st[id] = max(upd(lf, l, md, x, y, p), upd(rg, md+1, r, x, y, p));
    }
} B; // min - left

signed main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n-1; i++){
        int x, y; cin >> x >> y;
        adj[x].pb(y); adj[y].pb(x);
    }
    for(int i=1; i<=n; i++){
        s.insert({i, i});
        A.upd(1, 1, n, i, i, i);
        B.upd(1, 1, n, i, i, i);
    }

    for(int i=1; i<=m; i++){
        cin >> a[i]; int x = a[i]; // x - x+1
        ty[x] = 1-ty[x];

        if(ty[x]){ // mati - nyala
            auto it = s.lower_bound(pii(x+1, -1));
            auto it2 = it; it2--;
            int le = (*it2).fi; int ri = (*it).se;
            s.erase(it); s.erase(it2);
            s.insert({le, ri});

            int quel = A.que(1, 1, n, le, ri);
            int quer = B.que(1, 1, n, le, ri);
            A.upd(1, 1, n, le, ri, quel);
            B.upd(1, 1, n, le, ri, quer);
        } else { // nyala - mati
            auto it = s.lower_bound(pii(x+1, -1));
            it--;
            int le = (*it).fi; int ri = (*it).se;
            s.erase(it);
            s.insert(pii(le, x)); s.insert(pii(x+1, ri));
        }
        //for(auto in : s) cout << in.fi <<'p' << in.se << " p\n";
        //cout << i << " i\n";
    }

    while(q--){
        int id; cin >> id;
        l[id] = A.que(1, 1, n, id, id);
        r[id] = B.que(1, 1, n, id, id);
        //cout << l[id] << ' '<< r[id] << " lr\n";
        cout << r[id]-l[id]+1 << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 52316 KB Output is correct
2 Incorrect 9 ms 52392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52316 KB Output is correct
2 Correct 8 ms 52312 KB Output is correct
3 Correct 8 ms 52316 KB Output is correct
4 Correct 8 ms 52316 KB Output is correct
5 Correct 9 ms 52316 KB Output is correct
6 Correct 13 ms 52316 KB Output is correct
7 Correct 54 ms 53652 KB Output is correct
8 Correct 518 ms 65480 KB Output is correct
9 Correct 541 ms 65476 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 65552 KB Output is correct
2 Correct 362 ms 65360 KB Output is correct
3 Correct 367 ms 65360 KB Output is correct
4 Correct 368 ms 65364 KB Output is correct

Subtask #5
0 / 40.0

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