oj.uz

답안 #741578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741578 2023-05-14T11:29:38 Z maomao90 Advertisement 2 (JOI23_ho_t2) C++17
100 / 100
 338 ms 32972 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 2000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 500005;

int n;
ii xe[MAXN];
int inv[MAXN];
vii ord;
int ans;

#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
int sub[MAXN * 4], add[MAXN * 4];
void upd(int p, int s, int a, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        mxto(sub[u], s);
        mxto(add[u], a);
        return;
    }
    MLR;
    if (p <= mid) {
        upd(p, s, a, lc, lo, mid);
    } else {
        upd(p, s, a, rc, mid + 1, hi);
    }
    sub[u] = max(sub[lc], sub[rc]);
    add[u] = max(add[lc], add[rc]);
    cerr << u << ' ' << lo << ' ' << hi << ": " << sub[u] << '\n';
}
int qsub(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return sub[u];
    }
    MLR;
    int mx = -INF;
    if (s <= mid) {
        mxto(mx, qsub(s, e, lc, lo, mid));
    }
    if (e > mid) {
        mxto(mx, qsub(s, e, rc, mid + 1, hi));
    }
    return mx;
}
int qadd(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return add[u];
    }
    MLR;
    int mx = -INF;
    if (s <= mid) {
        mxto(mx, qadd(s, e, lc, lo, mid));
    }
    if (e > mid) {
        mxto(mx, qadd(s, e, rc, mid + 1, hi));
    }
    return mx;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    REP (i, 0, n) {
        cin >> xe[i].FI >> xe[i].SE;
    }
    sort(xe, xe + n);
    REP (i, 0, n) {
        ord.pb({xe[i].SE, i});
    }
    int prv = -1, ptr = 0;
    REP (i, 0, n) {
        if (xe[i].FI != prv) {
            prv = xe[i].FI;
            ptr++;
        }
        inv[ptr] = xe[i].FI;
        xe[i].FI = ptr;
    }
    sort(ALL(ord), greater<ii>());
    REP (i, 0, 4 * MAXN) {
        add[i] = sub[i] = -INF;
    }
    for (auto [_, i] : ord) {
        auto [x, e] = xe[i];
        cerr << x << ' ' << e << ' ' << inv[x] << '\n';
        cerr << " ? " << e - inv[x] << ' ' << e + inv[x] << '\n';
        int sub = qsub(x, n);
        cerr << ' ' << sub << '\n';
        if (sub >= e - inv[x]) {
            continue;
        }
        int add = qadd(1, x);
        cerr << ' ' << add << '\n';
        if (add >= e + inv[x]) {
            continue;
        }
        cerr << " ! " << x << ' ' << e - inv[x] << ' ' << e + inv[x] << '\n';
        upd(x, e - inv[x], e + inv[x]);
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:44:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:52:5: note: in expansion of macro 'MLR'
   52 |     MLR;
      |     ^~~
Main.cpp: In function 'int qsub(int, int, int, int, int)':
Main.cpp:44:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:66:5: note: in expansion of macro 'MLR'
   66 |     MLR;
      |     ^~~
Main.cpp: In function 'int qadd(int, int, int, int, int)':
Main.cpp:44:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:80:5: note: in expansion of macro 'MLR'
   80 |     MLR;
      |     ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 86 ms 18768 KB Output is correct
3 Correct 94 ms 21528 KB Output is correct
4 Correct 200 ms 26844 KB Output is correct
5 Correct 90 ms 22612 KB Output is correct
6 Correct 318 ms 25896 KB Output is correct
7 Correct 256 ms 26512 KB Output is correct
8 Correct 221 ms 30264 KB Output is correct
9 Correct 139 ms 27584 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15912 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 9 ms 15952 KB Output is correct
6 Correct 9 ms 15944 KB Output is correct
7 Correct 8 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 10 ms 15956 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 8 ms 15956 KB Output is correct
12 Correct 8 ms 15928 KB Output is correct
13 Correct 8 ms 15956 KB Output is correct
14 Correct 8 ms 15956 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15956 KB Output is correct
17 Correct 8 ms 15912 KB Output is correct
18 Correct 10 ms 15904 KB Output is correct

Subtask #3
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15912 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 9 ms 15952 KB Output is correct
6 Correct 9 ms 15944 KB Output is correct
7 Correct 8 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 10 ms 15956 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 8 ms 15956 KB Output is correct
12 Correct 8 ms 15928 KB Output is correct
13 Correct 8 ms 15956 KB Output is correct
14 Correct 8 ms 15956 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15956 KB Output is correct
17 Correct 8 ms 15912 KB Output is correct
18 Correct 10 ms 15904 KB Output is correct
19 Correct 9 ms 16024 KB Output is correct
20 Correct 9 ms 15972 KB Output is correct
21 Correct 9 ms 15956 KB Output is correct
22 Correct 8 ms 15956 KB Output is correct
23 Correct 9 ms 15920 KB Output is correct
24 Correct 8 ms 15956 KB Output is correct
25 Correct 8 ms 15960 KB Output is correct
26 Correct 9 ms 15956 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 86 ms 18768 KB Output is correct
3 Correct 94 ms 21528 KB Output is correct
4 Correct 200 ms 26844 KB Output is correct
5 Correct 90 ms 22612 KB Output is correct
6 Correct 318 ms 25896 KB Output is correct
7 Correct 256 ms 26512 KB Output is correct
8 Correct 221 ms 30264 KB Output is correct
9 Correct 139 ms 27584 KB Output is correct
10 Correct 9 ms 15956 KB Output is correct
11 Correct 8 ms 15956 KB Output is correct
12 Correct 8 ms 15912 KB Output is correct
13 Correct 8 ms 15956 KB Output is correct
14 Correct 9 ms 15952 KB Output is correct
15 Correct 9 ms 15944 KB Output is correct
16 Correct 8 ms 15956 KB Output is correct
17 Correct 8 ms 15956 KB Output is correct
18 Correct 10 ms 15956 KB Output is correct
19 Correct 8 ms 15956 KB Output is correct
20 Correct 8 ms 15956 KB Output is correct
21 Correct 8 ms 15928 KB Output is correct
22 Correct 8 ms 15956 KB Output is correct
23 Correct 8 ms 15956 KB Output is correct
24 Correct 8 ms 15956 KB Output is correct
25 Correct 8 ms 15956 KB Output is correct
26 Correct 8 ms 15912 KB Output is correct
27 Correct 10 ms 15904 KB Output is correct
28 Correct 9 ms 16024 KB Output is correct
29 Correct 9 ms 15972 KB Output is correct
30 Correct 9 ms 15956 KB Output is correct
31 Correct 8 ms 15956 KB Output is correct
32 Correct 9 ms 15920 KB Output is correct
33 Correct 8 ms 15956 KB Output is correct
34 Correct 8 ms 15960 KB Output is correct
35 Correct 9 ms 15956 KB Output is correct
36 Correct 218 ms 26068 KB Output is correct
37 Correct 284 ms 28900 KB Output is correct
38 Correct 324 ms 30860 KB Output is correct
39 Correct 303 ms 28156 KB Output is correct
40 Correct 331 ms 26780 KB Output is correct
41 Correct 338 ms 29624 KB Output is correct
42 Correct 262 ms 29880 KB Output is correct
43 Correct 278 ms 28788 KB Output is correct
44 Correct 295 ms 32972 KB Output is correct
45 Correct 289 ms 28752 KB Output is correct