oj.uz

Submission #163948

# Submission time Handle Problem Language Result Execution time Memory
163948 2019-11-16T11:29:29 Z combi1k1 Plahte (COCI17_plahte) C++14
0 / 160
 2000 ms 53964 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> contain[N];

int fr[N];
int to[N];

int cnt[N];
int res = 0;

void add(int x) {   cnt[x]++;   res += (cnt[x] == 1);   }
void rem(int x) {   cnt[x]--;   res -= (cnt[x] == 0);   }

int ans[N];

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;
    vector<int> col;

    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);

        fr[x] = y;
        to[y] = 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;

        col.push_back(k);

        contain[BIT2D::get(lower_bound(all(row),x) - row.begin() + 1,y)].push_back(k);
    }
    sort(all(col)); col.erase(unique(all(col)),col.end());

    for(int i = 1 ; i <= n ; ++i)
    for(int &x : contain[i])
        x = upper_bound(all(col),x) - col.begin();

    for(int i = 1 ; i <= n ; ++i)   if(!to[i])  {
        for(int x = i ; x ; x = fr[x])  {
            for(int c : contain[x]) add(c);
            ans[x] = res;
        }
        for(int x = i ; x ; x = fr[x])
            for(int c : contain[x]) rem(c);
    }

    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
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 25844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 29920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 39336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 53680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 53964 KB Time limit exceeded
2 Halted 0 ms 0 KB -