Submission #1177839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177839		faqinyeager	Advertisement 2 (JOI23_ho_t2)	C++17	0 / 100	3 ms	4932 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define ub(c, x) distance((c).begin(),lower_bound(c.begin(),c.end(), (x)))
#define ff first
#define ss second
#define N 200015
using namespace std;

const int inf = 1e9;

ll gcd(ll a, ll b){
    if(b == 0) return 1;
    return gcd(b, a % b);
}

ll n, m, s, t, l, k, ans = 0;
vector<pair<ll, ll>> G[N];

vector<ll> dijkstra(ll st){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<ll> dis;
    dis.resize(n + 1, 1e18);
    dis[st] = 0;
    pq.push({dis[st], st});
    while(!pq.empty()){
        pii now = pq.top();
        pq.pop();
        if(now.first != dis[now.second]) continue;
        for(auto x: G[now.second]){
            ll i = x.first, c = x.second;
            if(dis[i] > now.first + c){
                dis[i] = now.first + c;
                pq.push({dis[i], i});
            }
        }
    }
    return dis;
}

void CP2(){
    cin >> n >> m >> s >> t >> l >> k;
    rep(i, 0, m){
        ll a, b, c;
        cin >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    vector<ll> dis1 = dijkstra(s);
    vector<ll> dis2 = dijkstra(t);
    vector<ll> dis3 = dis2;

    //for(auto x: dis1) cout << x << ' '; cout << "\n\n";
    //for(auto x: dis2) cout << x << ' '; cout << "\n\n";    

    if(dis1[t] <= k){
        cout << n * (n - 1) / 2 << "\n"; return;
    }
    sort(dis2.begin(), dis2.end());
    rep(i, 1, n + 1){
        ll need = k - dis1[i] - l;
        ll can = upper_bound(dis2.begin(), dis2.end(), need) - dis2.begin();
        ans += can;
        if(dis3[i] <= need) ans--;
    }
    cout << ans << "\n";
}

void SA2(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    rep(i, 0, n){
        cin >> a[i];
        mp[a[i]] = i;
    }

    //rep(i, 0, n) cout << b[a[i]] << ' '; cout << "\n";

    int i = 0;
    while(i < n){
        int x = a[i];
        int y = mp[a[i]];
        for(; i <= y; i++) cout << x << ' ';
    }
}

void RT(){
    ll n, t;
    cin >> n >> t;
    vector<ll> v(n);
    rep(i, 0, n) cin >> v[i];
    
    rep(i, 0, n) v[i] %= t;
    sort(v.begin(), v.end());

    ll len = v[n - 1] - v[0];

    rep(i, 0, n - 1){
        len = min(len, t - (v[i + 1] - v[i]));
    }

    cout << (len + 1) / 2;
}

void AD2(){
    int n;
    cin >> n;
    vector<pair<int, int>> c;
    rep(i, 0, n){
        int a, b;
        cin >> a >> b;
        c.push_back({a - b, a + b});
    }

    sort(c.begin(), c.end());
    reverse(c.begin(), c.end());

    ll prev = INT_MIN, ans = 0ll;
    for(auto x: c){
        if(prev == INT_MIN){
            prev = x.ss;
        }else{
            if(prev > x.ss){
                ans++;
            }
        }
        prev = x.ss;
    }
    cout << ans;
}

int main() {
    int tc = 1;
    //cin >> tc;
    while(tc--) AD2();
}

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