Submission #1064966

#TimeUsernameProblemLanguageResultExecution timeMemory
1064966Dennis_JasonAdvertisement 2 (JOI23_ho_t2)C++14
59 / 100
2084 ms13648 KiB
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define pb push_back
#define MOD 1000000007
#define NMAX 500001
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>>  (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
/*
    ====================DEMONSTRATION======================

    =========================END===========================

 */
vector<int>tree_max;
vector<int>tree_min;
int n;
void build(int node,int st,int dr)
{
    if(st==dr)
    {
        tree_min[node]=INF;
        return;
    }
    int mid=(st+dr)/2;
    build(2*node,st,mid);
    build(2*node+1,mid+1,dr);
}
void init(int sz)
{
    sz;
    tree_max.resize(4*sz+1);
    tree_min.resize(4*sz+1);
    build(1,1,sz);
}

void update_max(int node,int st,int dr,int pos,int val)
{
    if(st==dr)
    {
        tree_max[node]=val;
        return;
    }
    int mid=(st+dr)/2;
    if(pos<=mid)
        update_max(2*node,st,mid,pos,val);
    else
        update_max(2*node+1,mid+1,dr,pos,val);
    tree_max[node]=max(tree_max[2*node],tree_max[2*node+1]);
}
void update_min(int node,int st,int dr,int pos,int val)
{
    if(st==dr)
    {
        tree_min[node]=val;
        return;
    }
    int mid=(st+dr)/2;
    if(pos<=mid)
        update_min(2*node,st,mid,pos,val);
    else
        update_min(2*node+1,mid+1,dr,pos,val);
    tree_min[node]=min(tree_min[2*node],tree_min[2*node+1]);
}

int query_max(int node,int st,int dr,int L,int R)
{
    if(st>R || dr<L)
        return 0;
    if(L<=st && dr<=R)
    {
        return tree_max[node];
    }
    int mid=(st+dr)/2;
    return max(query_max(2*node,st,mid,L,R),query_max(2*node+1,mid+1,dr,L,R));
}
int query_min(int node,int st,int dr,int L,int R)
{
    if(st>R || dr<L)
        return INF;
    if(st==dr)
        return tree_min[node];

    int mid=(st+dr)/2;
    return min(query_min(2*node,st,mid,L,R),query_min(2*node+1,mid+1,dr,L,R));
}

void update_max(int pos,int val)
{
    update_max(1,1,n,pos,val);
}
void update_min(int pos,int val)
{
    update_min(1,1,n,pos,val);
}

int query_max(int L,int R)
{
    if(L>R)
        return 0;
    return query_max(1,1,n,L,R);
}
int query_min(int L,int R)
{
    if(L>R)
        return INF;
    return query_min(1,1,n,L,R);
}

struct point{
    int first,second;
};
vector<point>v;

signed main() {

    cin>>n;
    v.resize(n+1);
    init(n);
    vector<int>aux(n+1);
    map<int,int>mp;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i].first>>v[i].second;
    }
    auto cmp1=[&](point a,point b)
    {
        return a.first<b.first;
    };
    sort(v.begin(),v.end(),cmp1);
    for(int i=1;i<=n;++i)
    {
        mp[v[i].first]=i;
    }
    auto cmp=[&](point a,point b)
    {
        return a.second>b.second;
    };
    sort(v.begin()+1,v.end(),cmp);
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int maxi=query_max(1,mp[v[i].first]);
        int mini=query_min(mp[v[i].first],n);
        if(v[i].first+v[i].second>maxi && v[i].first-v[i].second<mini)
        {
            ans++;
            update_max(mp[v[i].first],v[i].first+v[i].second);
            update_min(mp[v[i].first],v[i].first-v[i].second);
        }
    }
    cout<<ans;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void init(int)':
Main.cpp:55:5: warning: statement has no effect [-Wunused-value]
   55 |     sz;
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...