Submission #1124608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124608		FucKanh	Plahte (COCI17_plahte)	C++20	160 / 160	394 ms	56472 KiB

plahte

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

class IT {
vector<int> t,la;
int _n;
public:
    void init(int n) {
        _n = n;
        t.resize((n+2)*4,0);
        la.resize((n+2)*4,-1);
    }
    void pushdown(int v, int l, int r) {
        if (la[v] == -1) return;
        if (l!=r) {
            la[v*2] = la[v];
            la[v*2+1] = la[v];
        }
        t[v] = la[v];
        la[v] = -1;
    }
    void update(int v, int l, int r, int L, int R, int c) {
        pushdown(v,l,r);
        if (l==L && r == R) {
            la[v] = c;
            pushdown(v,l,r);
            return;
        }
        if (L > R) return;
        int mid = l + r >> 1;
        update(v*2,l,mid,L,min(mid,R),c);
        update(v*2+1,mid+1,r,max(L,mid+1),R,c);
    }
    int get(int v, int l, int r, int pos) {
        pushdown(v,l,r);
        if (l==r) return t[v];
        int mid = l + r >> 1;
        if (pos <= mid) {
            return get(v*2,l,mid,pos);
        }
        return get(v*2+1,mid+1,r,pos);
    }
};

const int maxn = 8e4 + 2;

int pa[maxn],ans[maxn];
set<int> st[maxn];
pii rec[maxn],colour[maxn];
vector<int> a[maxn];
map<int,int> mp;

void dfs(int u) {
    for (int v : a[u]) {
        dfs(v);
        if (st[v].size() > st[u].size()) swap(st[v],st[u]);
        for (int val : st[v]) st[u].insert(val);
    }
    ans[u] = st[u].size();
}


void solve() {
    int n,m; cin >> n >> m;
    vector<int> vec;
    priority_queue<pii,vector<pii>,greater<pii>> qin,qout;
    for (int i = 1; i <= n; i++) {
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        rec[i] = {y1,y2};
        vec.push_back(y1);
        vec.push_back(y2);
        qin.push({x1,-i});
        qout.push({x2,-i});
    }
    for (int i = 1; i <= m; i++) {
        int x1,y1,c; cin >> x1 >> y1 >> c;
        qin.push({x1,i});
        vec.push_back(y1);
        colour[i] = {y1,c};
    }
    sort(vec.begin(),vec.end());
    int pre = -1,cnt=0;
    for (int val : vec) {
        if (val==pre) continue;
        pre = val;
        cnt++;
        mp[val] = cnt;
    }
    for (int i = 1; i <= n; i++) rec[i] = make_pair(mp[rec[i].first], mp[rec[i].second]);
    for (int i = 1; i <= m; i++) colour[i].first = mp[colour[i].first];
    IT tree;
    tree.init(cnt);
    while (qin.size() && qout.size()) {
        if (qin.top().first <= qout.top().first) {
            int u = qin.top().second;
            qin.pop();
            if (u > 0) {
                int pos,c; tie(pos,c) = colour[u];
                int cha = tree.get(1,1,cnt, pos);
                if (cha) st[cha].insert(c);
            }
            else {
                u = -u;
                int l,r; tie(l,r) = rec[u];
                pa[u] = tree.get(1,1,cnt,l);
                assert( tree.get(1,1,cnt,l) == tree.get(1,1,cnt,r));
                a[pa[u]].push_back(u);
                tree.update(1,1,cnt,l,r,u);
            }
        }
        else {
            int u = qout.top().second;
            qout.pop();
            u = -u;

            int l,r;tie(l,r) = rec[u];
            tree.update(1,1,cnt,l,r,pa[u]);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (pa[i] == 0) dfs(i);
    }
    for (int i = 1;  i<= n; i++) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32