Submission #916531

#	Time	Username	Problem	Language	Result	Execution time	Memory
916531		WJR_dagger	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	137 ms	22784 KiB

Main

#include<bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define cout_line cout<<"line"<<__LINE__<<endl
#define cout_val(x) cout<<#x<<": "<<x<<endl
const long long mod=1e9+7;

/*
struct seg_tree{
    int l,r,mid,val,lz;
    seg_tree* ch[2];

    seg_tree(int a,int b,vector<int> &arr){
        l=a;r=b;
        if(l==r-1){
            val=arr[l];
            return;
        } 
        mid=(l+r)/2;
        ch[0]=new seg_tree(l,mid,arr);
        ch[1]=new seg_tree(mid,r,arr);
        pull();
        return;
    }

    void pull(){
        if(ch[0]->val==ch[1]->val)
        {
            val=ch[0]->val;
        }
        else{
            val=-1;
        }
        return;
    }
    void modify(int a,int b,int val_ch){
        int flag=0;
        if(a<=l && r<b)
        {
            if(val==-1){
                ch[0]->modify(a,b,val_ch);
                ch[1]->modify(a,b,val_ch);
            }
            else{
                val=max(val,val_ch);
            }
        }
        if(a<=l && mid<b){
            if(ch[0]->val==-1){
                ch[0]->modify(a,b,val_ch);
            }
            else{
                ch[0]->val=max(val,val_ch);
            }
        }
        if(a<=mid && r<b)
        {
            if(ch[1]->val==-1){
                ch[1]->modify(a,b,val_ch);
            }
            else{
                ch[1]->val=max(val,val_ch);
            }
        }
        pull();
        if(val==-1)
        {
            ch[0]->modify(a,b,val_ch);
            ch[1]->modify(a,b,val_ch);
            pull();
        }
        return;
    }
    void all(int a,int b){
        if(l==r-1) return;
        if(val==-1)
        {
            ch[0]->all();
            ch[1]->all();
        }
        else{
            ch[0]->modify(a,b,val);
            ch[1]->modify(a,b,val);
        }
        return;
    }
    void add(int idx,int val_add){
        if(l==idx){
            val+=val_add;
        }
        else if(l<idx && idx<mid){
            ch[0]->add(idx,val_add);
        }
        else
        {
            ch[1]->add(idx,val_add);
        }
        pull();
        return;
    }
};*/

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;cin>>n;
    vector<pair<int,int>> move;
    vector<pair<int,int>> move2;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        move.pb({a,b});
    }
    sort(move.begin(),move.end(),[](pair<int,int> a,pair<int,int> b){
        if(a.f==b.f) return a.s>b.s;
        return a.f<b.f;
    });
    int max=0,max_pos=INT_MIN;
    for(auto i:move)
    {
        if(i.f==max_pos) continue;
        if((llabs(max_pos-i.f))>(max-i.s)){
            move2.pb(i);
            max=i.s;
            max_pos=i.f;
        }
    }
    sort(move2.begin(),move2.end(),[](pair<int,int> a,pair<int,int> b){
        if(a.f==b.f) return a.s>b.s;
        return a.f>b.f;
    });
    max=0,max_pos=INT_MAX;
    int cnt=0;
    for(auto i:move2)
    {
        if(i.f==max_pos) continue;
        if((llabs(max_pos-i.f))>(max-i.s)){
            cnt++;
            max=i.s;
            max_pos=i.f;
        }
    }
    cout<<cnt;

    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31