Submission #782754

#	Time	Username	Problem	Language	Result	Execution time	Memory
782754		RecursiveCo	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	997 ms	88260 KiB

Main

// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long

int n;
void upd(vector<int>& segtree, int i, int x, int l=0, int r=n-1, int v=1) {
    if (l == r) segtree[v] = max(segtree[v], x);
    else {
        int middle = (l + r) / 2;
        if (i <= middle) upd(segtree, i, x, l, middle, 2 * v);
        else upd(segtree, i, x, middle + 1, r, 2 * v + 1);
        segtree[v] = max(segtree[2 * v], segtree[2 * v + 1]);
    }
}
int query(vector<int>& segtree, int ql, int qr, int l=0, int r=n-1, int v=1) {
    if (ql <= l && r <= qr) return segtree[v];
    if (r < ql || qr < l) return -1e18;
    int middle = (l + r) / 2;
    return max(
        query(segtree, ql, qr, l, middle, 2 * v),
        query(segtree, ql, qr, middle + 1, r, 2 * v + 1)
    );
}

signed main() {
    improvePerformance;
    //getTest;

    //eachTest {
        cin >> n;
        vector<array<int, 3>> people;
        vector<int> X;
        forto(n, i) {
            get(x);
            get(e);
            people.push_back({e, x, -1});
            X.push_back(x);
        }
        sortl(X);
        map<int, int> ind;
        int index = 0;
        forto(n, i) {
            if (ind.find(X[i]) == ind.end()) ind[X[i]] = index++;
        }
        forto(n, i) {
            people[i][2] = ind[people[i][1]];
        }
        vector<int> minustree(4 * n, -1e18);
        vector<int> plustree(4 * n, -1e18);
        int ans = 0;
        sortl(people);
        rev(people);
        forto(n, i) {
            bool found = false;
            int e = people[i][0];
            int x = people[i][1];
            int index = people[i][2];
            int minus = e - x;
            int plus = e + x;
            if (query(minustree, index, n - 1) >= minus) found = true;
            if (query(plustree, 0, index) >= plus) found = true;

            if (!found) {
                ans++;
                upd(minustree, index, minus);
                upd(plustree, index, plus);
            }
        }
        out(ans);
    //}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:48:9: note: in expansion of macro 'forto'
   48 |         forto(n, i) {
      |         ^~~~~
Main.cpp:10:23: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
Main.cpp:49:13: note: in expansion of macro 'get'
   49 |             get(x);
      |             ^~~
Main.cpp:10:23: warning: unnecessary parentheses in declaration of 'e' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
Main.cpp:50:13: note: in expansion of macro 'get'
   50 |             get(e);
      |             ^~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:57:9: note: in expansion of macro 'forto'
   57 |         forto(n, i) {
      |         ^~~~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:60:9: note: in expansion of macro 'forto'
   60 |         forto(n, i) {
      |         ^~~~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:68:9: note: in expansion of macro 'forto'
   68 |         forto(n, i) {
      |         ^~~~~

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