oj.uz

Submission #943060

# Submission time Handle Problem Language Result Execution time Memory
943060 2024-03-11T07:59:01 Z boyliguanhan Plahte (COCI17_plahte) C++17
160 / 160
 648 ms 77256 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
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(unordered_set<int>&a,unordered_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];
unordered_set<int> dfs(int n){
    unordered_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

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

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 29492 KB Output is correct
2 Correct 138 ms 28504 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 35376 KB Output is correct
2 Correct 183 ms 33236 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 55128 KB Output is correct
2 Correct 345 ms 45376 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 77256 KB Output is correct
2 Correct 648 ms 67668 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 75756 KB Output is correct
2 Correct 631 ms 64072 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct