oj.uz

Submission #619156

# Submission time Handle Problem Language Result Execution time Memory
619156 2022-08-02T10:17:17 Z Iwanttobreakfree Plahte (COCI17_plahte) C++17
160 / 160
 1186 ms 55464 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
#define pii pair<int,int>
const int INF=1e9+7;
const int MAX_N=80005;
int find_sheet2(int n,int l,int r,vector<int>& t,int x,int a){
    if(l==r&&t[n]>=x)return l;
    if(l>a||t[n]<x)return -1;
    int mid=(r+l)/2,ans=-1;
    if(mid+1<a&&t[(n<<1)+1]>=x)ans=find_sheet2((n<<1)+1,mid+1,r,t,x,a);
    if(ans==-1)ans=find_sheet2((n<<1),l,mid,t,x,a);
    return ans;
}
void pupd(int n,int l,int r,vector<int>& t,int a,int x){
    if(l>a||r<a)return;
    if(l==r&&l==a)t[n]=x;
    else{
        int mid=(r+l)/2;
        pupd(n<<1,l,mid,t,a,x);
        pupd((n<<1)+1,mid+1,r,t,a,x);
        t[n]=max(t[n<<1],t[(n<<1)+1]);
    }
}
int val(int n,int l,int r,vector<int>& t,int a,int b){
    if(l>b||r<a)return -1;
    if(l>=a&&r<=b)return t[n];
    else{
        int mid=(r+l)/2;
        int valls= val(n<<1,l,mid,t,a,b);
        int valrs= val((n<<1)+1,mid+1,r,t,a,b);
        return max(valls,valrs);
    }
}
int find_sheet(int a,int x,vector<int>& t,int cnt){
    int l=0,r=a,ans=0;
    while(l<=r){
        int mid=(r+l)/2;
        if(val(1,0,cnt-1,t,mid,a-1)>=x){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    return ans;
}
set<int> dfs(int a,vector<vector<int>>& g,vector<int>& ans,vector<set<int>>& color){
    set<int> cnt=color[a];
    for(int x:g[a]){
        set<int> cnt2=dfs(x,g,ans,color);
        if(cnt2.size()>cnt.size())swap(cnt,cnt2);
        for(int c:cnt2)cnt.insert(c);
    }
    ans[a]=cnt.size();
    return cnt;
}
int main(){
    int n,m,a,b,c,d;
    cin>>n>>m;
    vector<pair<pii,pii>> sheet(MAX_N);
    sheet[0]={{0,0},{INF,INF}};
    set<int> s;
    vector<pair<pii,int>> ball(m);
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c>>d;
        sheet[i]={{a,b},{c,d}};
        s.insert(b);
        s.insert(d);
    }
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        ball[i]={{a,b},c};
        s.insert(b);
    }
    s.insert(0);
    s.insert(INF);
    unordered_map<int,int> mp;
    mp.reserve(262144);
    int cnt=0;
    for(int x:s){
        mp[x]=cnt;
        cnt++;
    }
    vector<int> tr(4*cnt),active(cnt),ans(MAX_N);
    vector<pair<pair<pii,pii>,int>> q;
    vector<set<int>> color(MAX_N,set<int>());
    vector<vector<int>> g(MAX_N,vector<int>());
    //1 add sheet and search bigger sheet
    //3 delete
    //2 search first sheet of ith ball
    for(int i=0;i<=n;i++){
        q.push_back({{{sheet[i].first.first,sheet[i].first.second},{1,sheet[i].second.second}},i});
        q.push_back({{{sheet[i].second.first,sheet[i].second.second},{3,sheet[i].first.second}},i});
    }
    for(int j=0;j<m;j++){
        q.push_back({{ball[j].first,{2,ball[j].second}},j});
    }
    sort(q.begin(),q.end());
    for(int i=0;i<q.size();i++){
        int t=q[i].first.second.first,sheet=q[i].second,y1=q[i].first.first.second,y2=q[i].first.second.second;
        if(t==1){
            if(sheet!=0){
                int l=find_sheet(mp[y1],mp[y2],tr,cnt);
                g[active[l]].push_back(sheet);
            }
            //cout<<mp[y1]<<' '<<mp[y2]<<' '<<y1<<' '<<y2<<'\n';
            pupd(1,0,cnt-1,tr,mp[y1],mp[y2]);
            active[mp[y1]]=sheet;
        }if(t==3){
            pupd(1,0,cnt-1,tr,mp[y2],0);
            active[mp[y2]]=0;
        }if(t==2){
            int l=find_sheet(mp[y1]+1,mp[y1],tr,cnt);
            color[active[l]].insert(y2);
        }
    }
    /*for(int i=0;i<=n;i++){
        cout<<i<<':';
        for(int x:color[i])cout<<x<<' ';
        cout<<endl;
    }*/
    dfs(0,g,ans,color);
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<std::pair<int, int>, std::pair<int, int> >, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<q.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 20784 KB Output is correct
2 Correct 322 ms 21728 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 25464 KB Output is correct
2 Correct 377 ms 24768 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 38260 KB Output is correct
2 Correct 657 ms 33144 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 55464 KB Output is correct
2 Correct 1161 ms 47392 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1186 ms 51792 KB Output is correct
2 Correct 1101 ms 44724 KB Output is correct
3 Correct 8 ms 9684 KB Output is correct