Submission #917362

#	Time	Username	Problem	Language	Result	Execution time	Memory
917362		12345678	Plahte (COCI17_plahte)	C++17	96 / 160	321 ms	96272 KiB

plahte

#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 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32