oj.uz

Submission #163970

# Submission time Handle Problem Language Result Execution time Memory
163970 2019-11-16T12:46:42 Z combi1k1 Plahte (COCI17_plahte) C++14
160 / 160
 1025 ms 69484 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];
set<int>    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(int x : S[v])
            S[u].insert(x);
    }
    ans[u] = S[u].size();
}

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

    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)].insert(k);
    }

    dfs(0);

    for(int i = 1 ; i <= n ; ++i)   cout << ans[i] << "\n";
}
/*
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
*/

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 35316 KB Output is correct
2 Correct 248 ms 35836 KB Output is correct
3 Correct 32 ms 24148 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 40056 KB Output is correct
2 Correct 334 ms 39312 KB Output is correct
3 Correct 33 ms 24056 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 51956 KB Output is correct
2 Correct 557 ms 48604 KB Output is correct
3 Correct 32 ms 24188 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 69484 KB Output is correct
2 Correct 1025 ms 66384 KB Output is correct
3 Correct 34 ms 24312 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 67532 KB Output is correct
2 Correct 940 ms 63216 KB Output is correct
3 Correct 36 ms 24184 KB Output is correct