Submission #165587

#	Time	Username	Problem	Language	Result	Execution time	Memory
165587		Flying_dragon_02	Plahte (COCI17_plahte)	C++14	160 / 160	1538 ms	77880 KiB

plahte

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair< int, int > ii;

const int N = 240005;

const int inf = 1e9 + 5;

int n, m;

vector< int > X, Y, graph[2 * N];

pair < ii, ii > square[2 * N];
pair < ii, int > dart[2 * N];
set< int > st[2 * N];
set< int > :: iterator it;

bool vis[2 * N], used[2 * N];

struct IT {
    ii it[4 * N];
    IT() {
    }
    void build_tree(int k, int l, int r) {
        if(l == r) {
            it[k] = mp(-inf, -inf);
            return ;
        }
        int md = (l + r) >> 1;
        build_tree(k << 1, l, md);
        build_tree(k << 1 | 1, md + 1, r);
        it[k] = max(it[k << 1], it[k << 1 | 1]);
    }
    void update(int k, int l, int r, int pos, ii val) {
        if(pos < l || r < pos) return ;
        if(l == pos && pos == r) {
            it[k] = val;
            return ;
        }
        int md = (l + r) >> 1;
        update(k << 1, l, md, pos, val);
        update(k << 1 | 1, md + 1, r, pos, val);
        it[k] = max(it[k << 1], it[k << 1 | 1]);
    }
    ii get(int k, int l, int r, int L, int R) {
        if(R < l || r < L || L > R) return mp(-inf, -inf);
        if(L <= l && r <= R)
            return it[k];
        int md = (l + r) >> 1;
        return max( get(k << 1, l, md, L, R), get(k << 1 | 1, md + 1, r, L, R) );
    }
}tree;

int ans[2 * N];

void dfs(int u, int p) {
    //if(vis[u])
        //cout << u << " " << vis[u] << "\n";
    vis[u] = 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(v == p || vis[v]) continue;
        dfs(v, u);
        if(st[u].size() < st[v].size())
            st[u].swap(st[v]);
        for(it = st[v].begin(); it != st[v].end(); it++)
            st[u].insert(*it);
    }
    ans[u] = st[u].size();
}

vector < pair< ii, ii > > query[2 * N];

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    //freopen("PAINT.inp", "r", stdin);
    //freopen("PAINT.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> square[i].fi.fi >> square[i].fi.se >> square[i].se.fi >> square[i].se.se;
        if(square[i].fi.fi > square[i].se.fi) swap(square[i].fi.fi, square[i].se.fi);
        if(square[i].fi.se > square[i].se.se) swap(square[i].fi.se, square[i].se.se);
        X.pb(square[i].fi.fi);
        X.pb(square[i].se.fi);
        Y.pb(square[i].fi.se);
        Y.pb(square[i].se.se);
    }
    for(int i = 1; i <= m; i++) {
        cin >> dart[i].fi.fi >> dart[i].fi.se >> dart[i].se;
        X.pb(dart[i].fi.fi); Y.pb(dart[i].fi.se);
    }
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    sort(Y.begin(), Y.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());
    for(int i = 1; i <= n; i++) {
        int it1 = lower_bound(X.begin(), X.end(), square[i].fi.fi) - X.begin() + 1;
        query[it1].pb( mp( mp(square[i].fi.se, square[i].se.se), mp( 1, i ) ) );
        it1 = lower_bound(X.begin(), X.end(), square[i].se.fi) - X.begin() + 1;
        query[it1].pb( mp( mp(square[i].fi.se, square[i].se.se), mp( -1, i ) ) );
    }
    for(int i = 1; i <= m; i++) {
        int it1 = lower_bound(X.begin(), X.end(), dart[i].fi.fi) - X.begin() + 1;
        query[it1].pb( mp( mp( dart[i].fi.se, dart[i].fi.se ), mp( -inf, dart[i].se ) ) );
    }
    tree.build_tree(1, 1, (int)(Y.size()));
    for(int i = 1; i < 2 * N; i++)
        sort(query[i].begin(), query[i].end());
    for(int i = 1; i < N; i++) {
        for(int j = 0; j < query[i].size(); j++) {
            pair< ii, ii > type = query[i][j];
            int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
            //cout << "event1" << type.fi.fi << " " << type.fi.se << " " << type.se.fi << " " << type.se.se << "\n";
            if(type.se.fi > 0) {
         //  assert(it1 >= 1 && it1 <= (int)(Y.size()));
                tree.update(1, 1, (int)(Y.size()), it1, mp( type.fi.se, type.se.se ) );
            }
        }
        for(int j = 0; j < query[i].size(); j++) {
            pair< ii, ii > type = query[i][j];
            if(type.se.fi > 0) {
                int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
                int l = 1, r = it1 - 1, md;
                while(l < r) {
                   // cout << i << " " << l << " " << r << "\n";
                    md = (l + r + 1) >> 1;
                    if(tree.get(1, 1, (int)(Y.size()), md, it1 - 1).fi >= type.fi.se)
                        l = md;
                    else
                        r = md - 1;
                }
                ii temp = tree.get(1, 1, (int)(Y.size()), l, it1 - 1);
              //  cout << temp.fi << " " << temp.se << " " << type.fi.se << " " << type.se.se << "\n";
                if(temp.fi >= type.fi.se) {
                    used[type.se.se] = 1;
                    graph[temp.se].pb(type.se.se);
                }
                //if(i >= 226211)
                //cout << i << " " << l << " " << it1 << " " << temp.fi << " " << type.se.se << " " << temp.se << " " << type.fi.se << "\n";
            }
            else if(type.se.fi == -inf) {
                int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
                int l = 1, r = it1, md;
                while(l < r) {
                    md = (l + r + 1) >> 1;
                    if(tree.get(1, 1, (int)(Y.size()), md, it1).fi >= type.fi.se)
                        l = md;
                    else
                        r = md - 1;
                }
                //

                ii temp = tree.get(1, 1, (int)(Y.size()), l, it1);
                if(temp.fi >= type.fi.se) {
                    st[temp.se].insert(type.se.se);
                   // cout << "x:" << i << "hihixd" << temp.se << " " << type.se.se << " " << "y:" << temp.fi << " " << type.fi.se << "\n";
                }
            }
        }
        for(int j = 0; j < query[i].size(); j++) {
            pair< ii, ii > type = query[i][j];
            int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
            if(type.se.fi > 0 || type.se.fi == -inf) continue;
            assert(it1 >= 1 && it1 <= (int)(Y.size()));
            tree.update(1, 1, (int)(Y.size()), it1, mp( -inf, -inf ) );
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i] && used[i] == 0)
            dfs(i, i);
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int, int)':
plahte.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:117:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < query[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~
plahte.cpp:126:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < query[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~
plahte.cpp:167:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < query[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~

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