Submission #943022

#	Time	Username	Problem	Language	Result	Execution time	Memory
943022		boyliguanhan	Plahte (COCI17_plahte)	C++17	160 / 160	753 ms	76444 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
map<int,int>cc,c2;
map<int,tuple<vector<int>,vector<int>,vector<int>>>mp;
struct ST{
    int a,b,c,d,p;
}q[80100];
int v[1<<20],lz[1<<20],cnt,n,m,ans[80100];
void pd(int i,bool b){
    if(~lz[i]){
        v[i]=lz[i];
        if(b)
            lz[i*2+1]=lz[i*2]=lz[i];
        lz[i]=-1;
    }
}
int query(int i,int l,int r,int x){
    pd(i,l-r);
    if(l==r)return v[i];
    if(l+r>>1>=x)
        return query(i*2,l,l+r>>1,x);
    return query(i*2+1,l+r+2>>1,r,x);
}
void upd(int i,int l,int r,int tl, int tr,int x){
    pd(i,l-r);
    if(tl<=l&&r<=tr)
        return lz[i]=x,pd(i,l-r);
    if(l>tr||tl>r) return;
    upd(i*2,l,l+r>>1,tl,tr,x);
    upd(i*2+1,l+r+2>>1,r,tl,tr,x);
}
void merge(set<int>&a,set<int>b){
    if(a.size()<b.size())
        swap(a,b);
    for(auto i:b)
        a.insert(i);
    b.clear();
}
pair<int,int>pb[80100];
vector<int>given[80100],adj[80100];
set<int> dfs(int n){
    set<int>colors;
    for(auto i:given[n])
        colors.insert(i);
    for(auto i:adj[n])
        merge(colors,dfs(i));
    ans[n]=colors.size();
    return colors;
}
int main(){
    memset(lz,-1,sizeof lz);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>q[i].a>>q[i].b>>q[i].c>>q[i].d;
        cc[q[i].b],cc[q[i].d];
        get<0>(mp[q[i].a]).push_back(i);
        get<1>(mp[q[i].c]).push_back(i);
    }
    for(int i=1,a,b,c;i<=m;i++){
        cin>>a>>b>>c;
        get<2>(mp[a]).push_back(i);
        c2[c];pb[i]={b,c};
        cc[b];
    }
    for(auto&[i,j]:c2)
        j=++cnt;cnt=0;
    for(auto&[i,j]:cc)
        j=++cnt;
    for(auto[xx,ab]:mp){
        for(auto i:get<0>(ab))
            q[i].p=query(1,1,cnt,cc[q[i].b]),upd(1,1,cnt,cc[q[i].b],cc[q[i].d],i);
        for(auto i:get<2>(ab))
            given[query(1,1,cnt,cc[pb[i].first])].push_back(c2[pb[i].second]);
        for(auto i:get<1>(ab))
            upd(1,1,cnt,cc[q[i].b],cc[q[i].d],q[i].p);
    }
    for(int i=1;i<=n;i++)
        adj[q[i].p].push_back(i);
    dfs(0);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<'\n';
}

Compilation message (stderr)

plahte.cpp: In function 'int query(int, int, int, int)':
plahte.cpp:20:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     if(l+r>>1>=x)
      |        ~^~
plahte.cpp:21:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         return query(i*2,l,l+r>>1,x);
      |                            ~^~
plahte.cpp:22:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     return query(i*2+1,l+r+2>>1,r,x);
      |                        ~~~^~
plahte.cpp: In function 'void upd(int, int, int, int, int, int)':
plahte.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     upd(i*2,l,l+r>>1,tl,tr,x);
      |               ~^~
plahte.cpp:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     upd(i*2+1,l+r+2>>1,r,tl,tr,x);
      |               ~~~^~
plahte.cpp: In function 'int main()':
plahte.cpp:66:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   66 |     for(auto&[i,j]:c2)
      |     ^~~
plahte.cpp:67:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   67 |         j=++cnt;cnt=0;
      |                 ^~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32