oj.uz

Submission #906627

# Submission time Handle Problem Language Result Execution time Memory
906627 2024-01-14T15:10:13 Z a_l_i_r_e_z_a Examination (JOI19_examination) C++17
100 / 100
 1310 ms 15700 KB 
// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const ll maxn = 1e5 + 5;
const ll inf = 1e9 + 7;
ll n, q, cur, sq = 400, arr[maxn], ans[maxn];
pll a[maxn];
pair<pll, pll> b[maxn];
vector<ll> vec[maxn];

bool cmp(int i, int j){
    return a[i].F + a[i].S < a[j].F + a[j].S;
}

void del(int i){
    ll x = a[i].S;
    i = i / sq;
    vec[i].erase(find(all(vec[i]), x));
}

ll get(ll i, ll x){
    ll res = 0;
    for(; i < n; i += sq){
        int d = lower_bound(all(vec[i / sq]), x) - vec[i / sq].begin();
        res += vec[i / sq].size() - d;
    }
    return res;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> a[i].F;
        cin >> a[i].S;
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++){
        vec[i / sq].pb(a[i].S);
    }
    for(int i = 0; i < sq; i++) sort(all(vec[i]));
    for(int i = 0; i < q; i++){
        cin >> b[i].S.F >> b[i].S.S >> b[i].F.F;
        b[i].F.S = i;
    }
    sort(b, b + q);
    for(int i = 0; i < n; i++) arr[i] = i;
    sort(arr, arr + n, cmp);
    for(int i = 0; i < q; i++){
        ll Z = b[i].F.F, ind = b[i].F.S, A = b[i].S.F, B = b[i].S.S;
        while(cur < n && a[arr[cur]].F + a[arr[cur]].S < Z) del(arr[cur++]);
        int j = lower_bound(a, a + n, mp(A, 0ll)) - a;
        j = (j / sq) * sq;
        for(int k = j; ((1ll * k) < n) && ((1ll * k / sq) == (1ll * j / sq)); k++){
            if(a[k].F >= A && a[k].S >= B && a[k].F + a[k].S >= Z) ans[ind]++;
        }
        j += sq;
        if(j < n) ans[ind] += get(j, B);
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';

    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 8832 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8840 KB Output is correct
7 Correct 10 ms 8792 KB Output is correct
8 Correct 12 ms 8792 KB Output is correct
9 Correct 11 ms 8792 KB Output is correct
10 Correct 10 ms 8796 KB Output is correct
11 Correct 10 ms 8796 KB Output is correct
12 Correct 9 ms 8904 KB Output is correct
13 Correct 10 ms 8792 KB Output is correct
14 Correct 9 ms 8796 KB Output is correct
15 Correct 10 ms 8996 KB Output is correct
16 Correct 7 ms 8796 KB Output is correct
17 Correct 9 ms 8976 KB Output is correct
18 Correct 7 ms 8912 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 13064 KB Output is correct
2 Correct 863 ms 13140 KB Output is correct
3 Correct 866 ms 13064 KB Output is correct
4 Correct 655 ms 12372 KB Output is correct
5 Correct 467 ms 12324 KB Output is correct
6 Correct 416 ms 11600 KB Output is correct
7 Correct 1310 ms 12972 KB Output is correct
8 Correct 670 ms 12976 KB Output is correct
9 Correct 971 ms 12884 KB Output is correct
10 Correct 281 ms 12116 KB Output is correct
11 Correct 401 ms 12052 KB Output is correct
12 Correct 149 ms 11088 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 13064 KB Output is correct
2 Correct 863 ms 13140 KB Output is correct
3 Correct 866 ms 13064 KB Output is correct
4 Correct 655 ms 12372 KB Output is correct
5 Correct 467 ms 12324 KB Output is correct
6 Correct 416 ms 11600 KB Output is correct
7 Correct 1310 ms 12972 KB Output is correct
8 Correct 670 ms 12976 KB Output is correct
9 Correct 971 ms 12884 KB Output is correct
10 Correct 281 ms 12116 KB Output is correct
11 Correct 401 ms 12052 KB Output is correct
12 Correct 149 ms 11088 KB Output is correct
13 Correct 696 ms 13532 KB Output is correct
14 Correct 876 ms 13452 KB Output is correct
15 Correct 857 ms 12880 KB Output is correct
16 Correct 521 ms 12624 KB Output is correct
17 Correct 417 ms 12628 KB Output is correct
18 Correct 418 ms 11592 KB Output is correct
19 Correct 706 ms 13500 KB Output is correct
20 Correct 787 ms 13484 KB Output is correct
21 Correct 709 ms 13392 KB Output is correct
22 Correct 260 ms 12132 KB Output is correct
23 Correct 411 ms 12148 KB Output is correct
24 Correct 148 ms 11092 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 8832 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8840 KB Output is correct
7 Correct 10 ms 8792 KB Output is correct
8 Correct 12 ms 8792 KB Output is correct
9 Correct 11 ms 8792 KB Output is correct
10 Correct 10 ms 8796 KB Output is correct
11 Correct 10 ms 8796 KB Output is correct
12 Correct 9 ms 8904 KB Output is correct
13 Correct 10 ms 8792 KB Output is correct
14 Correct 9 ms 8796 KB Output is correct
15 Correct 10 ms 8996 KB Output is correct
16 Correct 7 ms 8796 KB Output is correct
17 Correct 9 ms 8976 KB Output is correct
18 Correct 7 ms 8912 KB Output is correct
19 Correct 869 ms 13064 KB Output is correct
20 Correct 863 ms 13140 KB Output is correct
21 Correct 866 ms 13064 KB Output is correct
22 Correct 655 ms 12372 KB Output is correct
23 Correct 467 ms 12324 KB Output is correct
24 Correct 416 ms 11600 KB Output is correct
25 Correct 1310 ms 12972 KB Output is correct
26 Correct 670 ms 12976 KB Output is correct
27 Correct 971 ms 12884 KB Output is correct
28 Correct 281 ms 12116 KB Output is correct
29 Correct 401 ms 12052 KB Output is correct
30 Correct 149 ms 11088 KB Output is correct
31 Correct 696 ms 13532 KB Output is correct
32 Correct 876 ms 13452 KB Output is correct
33 Correct 857 ms 12880 KB Output is correct
34 Correct 521 ms 12624 KB Output is correct
35 Correct 417 ms 12628 KB Output is correct
36 Correct 418 ms 11592 KB Output is correct
37 Correct 706 ms 13500 KB Output is correct
38 Correct 787 ms 13484 KB Output is correct
39 Correct 709 ms 13392 KB Output is correct
40 Correct 260 ms 12132 KB Output is correct
41 Correct 411 ms 12148 KB Output is correct
42 Correct 148 ms 11092 KB Output is correct
43 Correct 698 ms 15452 KB Output is correct
44 Correct 696 ms 15700 KB Output is correct
45 Correct 894 ms 15404 KB Output is correct
46 Correct 530 ms 13872 KB Output is correct
47 Correct 420 ms 13876 KB Output is correct
48 Correct 356 ms 11348 KB Output is correct
49 Correct 1295 ms 15200 KB Output is correct
50 Correct 524 ms 15216 KB Output is correct
51 Correct 796 ms 15188 KB Output is correct
52 Correct 250 ms 13652 KB Output is correct
53 Correct 429 ms 12884 KB Output is correct