oj.uz

Submission #966431

# Submission time Handle Problem Language Result Execution time Memory
966431 2024-04-19T20:48:42 Z oviyan_gandhi Examination (JOI19_examination) C++17
2 / 100
 3000 ms 11048 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef tree<pii, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oset;

#define N 100000
#define S 320
pii s[N]; // {s, t}

struct Query {
    int x, y, c, i;
    bool operator < (const Query &o) const {
        if (x/S != o.x/S) return x > o.x;
        return y < o.y;
    }
};
Query qu[N];
int ans[N];

set<pii> st, disc; // {t, i}
oset sc; // {s + t, i}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> s[i].first >> s[i].second;
    sort(s, s+n);
    for (int i = 0; i < q; i++){
        cin >> qu[i].x >> qu[i].y >> qu[i].c;
        qu[i].i = i;
        qu[i].x = lower_bound(s, s+n, make_pair(qu[i].x, 0LL)) - s;
    }
    sort(qu, qu+q);
    int idx = n;
    for (int i = 0; i < q; i++){
        while (idx-1 >= qu[i].x){
            idx--;
            st.insert({s[idx].second, idx});
            sc.insert({s[idx].first + s[idx].second, idx});
        }
        while (idx < qu[i].x){
            auto it = st.find({s[idx].second, idx});
            if (it != st.end()){
                st.erase(it);
                sc.erase({s[idx].first + s[idx].second, idx});
            } else disc.erase({s[idx].second, idx});
            idx++;
        }
        while (!st.empty() && st.begin()->first < qu[i].y){
            int j = st.begin()->second;
            st.erase(st.begin());
            sc.erase({s[j].first + s[j].second, j});
            disc.insert({s[j].second, j});
        }
        while (!disc.empty() && prev(disc.end())->first >= qu[i].y){
            int j = prev(disc.end())->second;
            disc.erase(prev(disc.end()));
            st.insert({s[j].second, j});
            sc.insert({s[j].first + s[j].second, j});
        }
        ans[qu[i].i] = sc.size() - sc.order_of_key({qu[i].c, 0});
    }
    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 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 75 ms 4940 KB Output is correct
8 Correct 76 ms 4948 KB Output is correct
9 Correct 95 ms 4948 KB Output is correct
10 Correct 69 ms 4820 KB Output is correct
11 Correct 34 ms 4952 KB Output is correct
12 Correct 32 ms 4796 KB Output is correct
13 Correct 84 ms 4984 KB Output is correct
14 Correct 77 ms 4896 KB Output is correct
15 Correct 82 ms 4780 KB Output is correct
16 Correct 3 ms 4952 KB Output is correct
17 Correct 60 ms 4948 KB Output is correct
18 Correct 5 ms 4952 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 11048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 11048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 75 ms 4940 KB Output is correct
8 Correct 76 ms 4948 KB Output is correct
9 Correct 95 ms 4948 KB Output is correct
10 Correct 69 ms 4820 KB Output is correct
11 Correct 34 ms 4952 KB Output is correct
12 Correct 32 ms 4796 KB Output is correct
13 Correct 84 ms 4984 KB Output is correct
14 Correct 77 ms 4896 KB Output is correct
15 Correct 82 ms 4780 KB Output is correct
16 Correct 3 ms 4952 KB Output is correct
17 Correct 60 ms 4948 KB Output is correct
18 Correct 5 ms 4952 KB Output is correct
19 Execution timed out 3047 ms 11048 KB Time limit exceeded
20 Halted 0 ms 0 KB -