Submission #1301321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301321		mine255	Plahte (COCI17_plahte)	C++17	160 / 160	283 ms	55296 KiB

plahte

#include <bits/stdc++.h>
#define _FILE "TEMP"
#define ll long long
#define ii pair<int,int>
#define lii pair<ll,ll>
#define fi first
#define se second
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

int n,m;

struct rectangle {
    int x,y,u,v;
} a[100007];

struct point {
    int x,y,k; 
} b[100007];

vector<int> cmp_x,cmp_y;

int st[1200007];
int lazy[1200007];

void push(int id) {
    if (lazy[id] == -1) return;

    st[2*id] = lazy[2*id] = st[2*id+1] = lazy[2*id+1] = lazy[id];
    lazy[id] = -1;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id] = 0;
        lazy[id] = -1;
        return;
    }

    int mid = (l + r) >> 1;
    build(2*id,l,mid);
    build(2*id+1,mid+1,r);

    st[id] = 0;
    lazy[id] = -1;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (l > v || u > r) return;
    if (u <= l && r <= v) {
        st[id] = val;
        lazy[id] = val;
        return;
    }

    int mid = (l + r) >> 1;
    push(id);
    update(2*id,l,mid,u,v,val);
    update(2*id+1,mid+1,r,u,v,val);

    st[id] = max(st[2*id],st[2*id+1]);
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || u > r) return 0;
    if (u <= l && r <= v) return st[id];

    int mid = (l + r) >> 1;
    push(id);

    return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}

vector<int> rec_add[300007], rec_del[300007];
vector<int> point[300007];

vector<int> adj[100007];
int par[100007];
set<int> s[100007];
bool is_root[100007];

int res[100007];

void dfs(int i) {
    for (int j : adj[i]) {
        dfs(j);
        if (s[i].size() < s[j].size()) swap(s[i],s[j]);
        s[i].insert(s[j].begin(),s[j].end());
        s[j].clear();
    }

    res[i] = s[i].size();
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    #ifdef EMERGENCY_DEBUG
    freopen(_FILE".inp","r",stdin);
    freopen(_FILE".out","w",stdout);
    #endif

    cin >> n >> m;

    for (int i=1; i<=n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].u >> a[i].v;
        cmp_x.push_back(a[i].x);
        cmp_y.push_back(a[i].y);
        cmp_x.push_back(a[i].u);
        cmp_y.push_back(a[i].v);
    }

    for (int i=1; i<=m; i++) {
        cin >> b[i].x >> b[i].y >> b[i].k;

        cmp_x.push_back(b[i].x);
        cmp_y.push_back(b[i].y);
    }

    sort(cmp_x.begin(),cmp_x.end());
    sort(cmp_y.begin(),cmp_y.end());

    for (int i=1; i<=n; i++) {
        a[i].x = lower_bound(cmp_x.begin(),cmp_x.end(),a[i].x) - cmp_x.begin() + 1;
        a[i].y = lower_bound(cmp_y.begin(),cmp_y.end(),a[i].y) - cmp_y.begin() + 1;
        a[i].u = lower_bound(cmp_x.begin(),cmp_x.end(),a[i].u) - cmp_x.begin() + 1;
        a[i].v = lower_bound(cmp_y.begin(),cmp_y.end(),a[i].v) - cmp_y.begin() + 1;

        rec_add[a[i].x].push_back(i);
        rec_del[a[i].u].push_back(i);

        is_root[i] = 1;
    }

    for (int i=1; i<=m; i++) {
        b[i].x = lower_bound(cmp_x.begin(),cmp_x.end(),b[i].x) - cmp_x.begin() + 1;
        b[i].y = lower_bound(cmp_y.begin(),cmp_y.end(),b[i].y) - cmp_y.begin() + 1;
        
        point[b[i].x].push_back(i);
    }

    for (int i=1; i<=(int)cmp_x.size(); i++) {
        for (int j : rec_add[i]) {
            int cur = get(1,1,cmp_y.size(),a[j].y,a[j].v);
            if (cur != 0) {
                is_root[j] = 0;
                par[j] = cur;
                adj[cur].push_back(j);
            }

            update(1,1,cmp_y.size(),a[j].y,a[j].v,j);
        }

        for (int j : point[i]) {
            int cur = get(1,1,cmp_y.size(),b[j].y,b[j].y);

            if (cur != 0) {
                s[cur].insert(b[j].k);
            }
        }

        for (int j : rec_del[i]) {
            update(1,1,cmp_y.size(),a[j].y,a[j].v,par[j]);
        }
    }

    for (int i=1; i<=n; i++) {
        if (is_root[i]) dfs(i);
    }

    for (int i=1; i<=n; i++) {
        cout << res[i] << '\n';
    }

    return 0;
}

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