Submission #1064959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064959		Dennis_Jason	Advertisement 2 (JOI23_ho_t2)	C++14	59 / 100	2049 ms	10952 KiB

Main

#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 250001
#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===========================
 
 */
class segtree{
private:
    int n;
    vector<int>tree_max;
    vector<int>tree_min;
 
public:
    void init(int sz)
    {
        n=sz;
        tree_max.resize(4*sz+1);
        tree_min.resize(4*sz+1);
      	build(1,1,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 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;
        int left= query_max(2*node,st,mid,L,R);
        int right= query_max(2*node+1,mid+1,dr,L,R);
        return max(left,right);
    }
    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;
        int left= query_min(2*node,st,mid,L,R);
        int right=query_min(2*node+1,mid+1,dr,L,R);
        return min(left,right);
    }
 
    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);
    }
};
int n;
vector<pii>v;
segtree seg;
signed main() {
 
    cin>>n;
    v.resize(n+1);
    unordered_map<int,int>mp;
    seg.init(n);
    vector<int>aux(n+1);
    for(int i=1;i<=n;++i)
    {
        cin>>v[i].first>>v[i].second;
        aux[i]=v[i].first;
    }
    sort(aux.begin()+1,aux.end());
    for(int i=1;i<=n;++i)
    {
        mp[aux[i]]=i;
    }
    auto cmp=[&](pii a,pii 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=seg.query_max(1,mp[v[i].first]);
        int mini=seg.query_min(mp[v[i].first],n);
        if(v[i].first+v[i].second>maxi && v[i].first-v[i].second<mini)
        {
            ans++;
            seg.update_max(mp[v[i].first],v[i].first+v[i].second);
            seg.update_min(mp[v[i].first],v[i].first-v[i].second);
        }
    }
    cout<<ans;
 
    return 0;
}

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