Submission #1256207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256207		minhpk	Worst Reporter 2 (JOI16_worst_reporter2)	C++20	100 / 100	225 ms	57008 KiB

worst_reporter2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
struct node{
     int id,val,type;
};
vector <node> z;
bool cmp(node a,node b){
     if (a.val==b.val){
         return a.type<b.type;
     }
     return a.val<b.val;
}
int prefix[1000005];
int f[4000005];
int lazy[4000005];
int bruh=1e16;
void build(int id,int l,int r){
    if (l==r){
        f[id]=prefix[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    f[id]=min(f[id*2],f[id*2+1]);
}
void update(int id,int l,int r,int x,int y,int val){
     if (x>r || y<l){
         return;
     }
     if (l>=x && y>=r){
         f[id]+=val;
         lazy[id]+=val;
         return;
     }
     int mid=(l+r)/2;
     update(id*2,l,mid,x,y,val);
     update(id*2+1,mid+1,r,x,y,val);
     f[id]=min(f[id*2],f[id*2+1])+lazy[id];
}
int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return bruh;
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid=(l+r)/2;
    return min(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y))+lazy[id];
}
vector<int> st[1000005];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    z.push_back({69,-bruh,1});
    for (int i=1;i<=a;i++){
         int x,y;
         cin >> x >> y;
         z.push_back({x,y,1});
    }
    for (int i=1;i<=a;i++){
         int x,y;
         cin >> x >> y;
         z.push_back({x,y,2});
    }
    sort(z.begin(),z.end(),cmp);
    int n=2*a;
    for (int i=1;i<=n;i++){
         prefix[i]=prefix[i-1]+(z[i].type==1 ? 1:-1);
    }
    int res=0;
    build(1,1,n);
    for (int i=1;i<=n;i++){
//            cerr << z[i].type << " ";
         if (z[i].type==1){
             st[z[i].id].push_back(i);
         }else{
             if (st[z[i].id].size()){
                 int pos=st[z[i].id].back();
                 int sadge=get(1,1,n,pos,i-1);
                 if (sadge==0){
                     continue;
                 }else{
                     res++;
                     update(1,1,n,pos,i-1,-1);
                     st[z[i].id].pop_back();
                 }
             }
         }

    }
//    cout << "\n";
    cout << a-res << "\n";
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40