oj.uz

Submission #917362

# Submission time Handle Problem Language Result Execution time Memory
917362 2024-01-28T02:30:42 Z 12345678 Plahte (COCI17_plahte) C++17
96 / 160
 321 ms 96272 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=8e4+5, mx=160005;
int n, m, a[nx], b[nx], c[nx], d[nx], x[nx], y[nx], cl[nx], tx, ty, tc, pa[nx], in[nx], out[nx], t, id[nx], sz[nx], cnt[nx], ans[nx], res;
map<int, int> mpx, mpy, mpc;
vector<int> add[mx], rem[mx], pts[mx], g[mx], s[nx];

struct fenwick
{
    int d[mx];
    void add(int i, int vl)
    {
        while (i<mx) d[i]+=vl, i+=(i&-i); 
    }
    int query(int i)
    {
        int res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
} f;

void dfs(int u)
{
    in[u]=++t;
    id[t]=u;
    sz[u]=1+s[u].size();
    for (auto v:g[u]) dfs(v), sz[u]+=sz[v];
    out[u]=t;
}

void insert(int vl)
{
    if (cnt[vl]==0) res++;
    cnt[vl]++;
}

void erase(int vl)
{
    if (cnt[vl]==1) res--;
    cnt[vl]--;
}

void sack(int u, bool del)
{
    //cout<<"graph "<<u<<'\n';
    pair<int, int> hv={-1, -1};
    for (auto v:g[u]) hv=max(hv, {sz[v], v});
    for (auto v:g[u]) if (v!=hv.second) sack(v, 1);
    if (hv.second!=-1) sack(hv.second, 0);
    for (auto tmp:s[u]) insert(tmp);
    for (auto v:g[u]) if (v!=hv.second) for (int i=in[v]; i<=out[v]; i++) for (auto tmp:s[id[i]]) insert(tmp);
    ans[u]=res;
    if (del) for (int i=in[u]; i<=out[u]; i++) for (auto tmp:s[id[i]]) erase(tmp);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i]>>d[i], mpx[a[i]]=0, mpy[b[i]]=0, mpx[c[i]]=0, mpy[d[i]]=0;
    for (int i=1; i<=m; i++) cin>>x[i]>>y[i]>>cl[i], mpx[x[i]]=0, mpy[y[i]]=0, mpc[cl[i]];
    for (auto &[k, idx]:mpx) idx=++tx;
    for (auto &[k, idx]:mpy) idx=++ty;
    for (auto &[k, idx]:mpc) idx=++tc;
    for (int i=1; i<=n; i++) a[i]=mpx[a[i]], b[i]=mpy[b[i]], c[i]=mpx[c[i]], d[i]=mpy[d[i]], add[a[i]].push_back(i), rem[c[i]].push_back(i);
    for (int i=1; i<=m; i++) x[i]=mpx[x[i]], y[i]=mpy[y[i]], cl[i]=mpc[cl[i]], pts[x[i]].push_back(i);
    for (int i=1; i<mx; i++)
    {
        for (auto idx:add[i])
        {
            pa[idx]=f.query(b[idx]);
            g[pa[idx]].push_back(idx);
            f.add(b[idx], idx-pa[idx]);
            f.add(d[idx]+1, pa[idx]-idx);
        }
        for (auto idx:pts[i]) s[f.query(y[idx])].push_back(cl[idx]);
        for (auto idx:rem[i]) f.add(b[idx], pa[idx]-idx), f.add(d[idx]+1, idx-pa[idx]);
    }
    dfs(0);
    sack(0, 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 122 ms 33104 KB Output is correct
2 Correct 125 ms 32716 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 36760 KB Output is correct
2 Correct 163 ms 35600 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 48188 KB Output is correct
2 Correct 321 ms 43760 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 288 ms 95572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 283 ms 96272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -