제출 #1074905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074905		ivaziva	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	921 ms	53008 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 500001

int n;
vector<pair<int,int>> vec;
map<int,int> kompresija;
int seg[MAXN*4][2];

void update(int pos,int node,int l,int r,int poz,int val)
{
    if (l==r) seg[node][pos]=val;
    else
    {
        int mid=(l+r)/2;
        if (poz<=mid) update(pos,2*node,l,mid,poz,val);
        else update(pos,2*node+1,mid+1,r,poz,val);
        seg[node][pos]=max(seg[2*node][pos],seg[2*node+1][pos]);
    }
}

int query(int pos,int node,int l,int r,int a,int b)
{
    if (a>b) return -INT_MAX;
    if (l==a and r==b) return seg[node][pos];
    int mid=(l+r)/2;
    return max(query(pos,2*node,l,mid,a,min(b,mid)),query(pos,2*node+1,mid+1,r,max(a,mid+1),b));
}

int main()
{
    for (int i=0;i<4*MAXN;i++) seg[i][0]=seg[i][1]=-INT_MAX;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int x,e;cin>>x>>e;
        vec.push_back({e,x});
        kompresija[x]=1;
    }
    sort(vec.rbegin(),vec.rend());
    int idx=0;
    for (auto&p:kompresija) {idx++;p.second=idx;}
    int ans=0;
    for (int i=0;i<n;i++)
    {
        int poz=kompresija[vec[i].second];
        if (query(0,1,1,idx,poz,idx)>=vec[i].first-vec[i].second) continue;
        if (query(1,1,1,idx,1,poz)>=vec[i].first+vec[i].second) continue;
        ans++;
        update(0,1,1,idx,poz,vec[i].first-vec[i].second);
        update(1,1,1,idx,poz,vec[i].first+vec[i].second);
    }
    cout<<ans<<endl;
}

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