oj.uz

Submission #165415

# Submission time Handle Problem Language Result Execution time Memory
165415 2019-11-27T07:15:11 Z combi1k1 Plahte (COCI17_plahte) C++14
160 / 160
 1198 ms 72080 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x)  x.begin(),x.end()
#define sz(x)   x.size()

const int   N   = 160010;

namespace BIT2D {
    vector<int> val[N];
    vector<int> bit[N];

    void ini()  {
        for(int i = 1 ; i < N ; ++i)    {
            sort(all(val[i]));
            val[i].resize(unique(all(val[i])) - val[i].begin());
            bit[i].resize(val[i].size() + 5);
        }
    }
    void add(int x,int y)   {
        for(; x > 0 ; x -= x & -x)
            val[x].push_back(y);
    }
    void upd(int x,int y,int v) {
        for(; x > 0 ; x -= x & -x)  {
            int p = upper_bound(all(val[x]),y) - val[x].begin();
            for(; p > 0 ; p -= p & -p)
                bit[x][p] += v;
        }
    }
    int get(int x,int y)    {
        int ans = 0;
        for(; x < N ; x += x & -x)  {
            int p = lower_bound(all(val[x]),y)  - val[x].begin() + 1;
            int K = bit[x].size();
            for(; p < K ; p += p & -p)
                ans += bit[x][p];
        }
        return  ans;
    }
};

struct Rect {
    int l, r;
    int u, d;
    int idx;
}   Sheet[N];

vector<int> g[N];
unordered_map<int,bool> S[N];

int ans[N];

void dfs(int u) {
    for(int v : g[u])   {
        dfs(v);
        if (S[u].size() < S[v].size())
            S[u].swap(S[v]);
        for(auto it : S[v])
            S[u][it.first] = 1;
    }
    ans[u] = S[u].size();
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef ncombi
    freopen("PAINT.inp","r",stdin);
    freopen("PAINT.out","w",stdout);
    #endif // ncombi

    int n;  cin >> n;
    int m;  cin >> m;

    vector<int> row;

    for(int i = 0 ; i < n ; ++i)    {
        cin >> Sheet[i].l >> Sheet[i].u;
        cin >> Sheet[i].r >> Sheet[i].d;

        Sheet[i].idx = i + 1;

        Sheet[i].l--;
        Sheet[i].u--;

        row.push_back(Sheet[i].l);
        row.push_back(Sheet[i].r);
    }
    sort(all(row)); row.erase(unique(all(row)),row.end());

    for(int i = 0 ; i < n ; ++i)    {
        Sheet[i].l = upper_bound(all(row),Sheet[i].l) - row.begin();
        Sheet[i].r = upper_bound(all(row),Sheet[i].r) - row.begin();

        BIT2D::add(Sheet[i].l,Sheet[i].u);
        BIT2D::add(Sheet[i].l,Sheet[i].d);
        BIT2D::add(Sheet[i].r,Sheet[i].u);
        BIT2D::add(Sheet[i].r,Sheet[i].d);
    }

    BIT2D::ini();

    sort(Sheet,Sheet + n,[&](const Rect &a,const Rect &b)   {
        return  a.l < b.l;
    });

    for(int i = 0 ; i < n ; ++i)    {
        int x = Sheet[i].idx;
        int y = BIT2D::get(Sheet[i].r,Sheet[i].d);

        g[y].push_back(x);

        BIT2D::upd(Sheet[i].l,Sheet[i].u,x - y);
        BIT2D::upd(Sheet[i].r,Sheet[i].d,x - y);
        BIT2D::upd(Sheet[i].l,Sheet[i].d,y - x);
        BIT2D::upd(Sheet[i].r,Sheet[i].u,y - x);
    }

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;
        int k;  cin >> k;

        S[BIT2D::get(lower_bound(all(row),x) - row.begin() + 1,y)][k] = 1;
    }

    dfs(0);

    for(int i = 1 ; i <= n ; ++i)   cout << ans[i] << "\n";
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 36672 KB Output is correct
2 Correct 257 ms 37012 KB Output is correct
3 Correct 34 ms 25592 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 41556 KB Output is correct
2 Correct 332 ms 40696 KB Output is correct
3 Correct 35 ms 25464 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 54328 KB Output is correct
2 Correct 561 ms 49776 KB Output is correct
3 Correct 39 ms 25336 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 72080 KB Output is correct
2 Correct 1024 ms 66256 KB Output is correct
3 Correct 34 ms 25592 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 70808 KB Output is correct
2 Correct 1198 ms 62700 KB Output is correct
3 Correct 35 ms 25464 KB Output is correct