Submission #885770

#	Time	Username	Problem	Language	Result	Execution time	Memory
885770		ByeWorld	Synchronization (JOI13_synchronization)	C++14	30 / 100	557 ms	65552 KiB

synchronization

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