oj.uz

Submission #966428

# Submission time Handle Problem Language Result Execution time Memory
966428 2024-04-19T20:36:37 Z oviyan_gandhi Examination (JOI19_examination) C++17
2 / 100
 3000 ms 10636 KB 
#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 4440 KB Output is correct
3 Correct 1 ms 4444 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 4444 KB Output is correct
7 Correct 83 ms 4736 KB Output is correct
8 Correct 81 ms 4892 KB Output is correct
9 Correct 84 ms 4824 KB Output is correct
10 Correct 76 ms 4912 KB Output is correct
11 Correct 43 ms 4948 KB Output is correct
12 Correct 36 ms 4960 KB Output is correct
13 Correct 83 ms 4936 KB Output is correct
14 Correct 87 ms 4892 KB Output is correct
15 Correct 85 ms 4820 KB Output is correct
16 Correct 4 ms 4956 KB Output is correct
17 Correct 54 ms 4948 KB Output is correct
18 Correct 4 ms 4956 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 10636 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 3080 ms 10636 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 4440 KB Output is correct
3 Correct 1 ms 4444 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 4444 KB Output is correct
7 Correct 83 ms 4736 KB Output is correct
8 Correct 81 ms 4892 KB Output is correct
9 Correct 84 ms 4824 KB Output is correct
10 Correct 76 ms 4912 KB Output is correct
11 Correct 43 ms 4948 KB Output is correct
12 Correct 36 ms 4960 KB Output is correct
13 Correct 83 ms 4936 KB Output is correct
14 Correct 87 ms 4892 KB Output is correct
15 Correct 85 ms 4820 KB Output is correct
16 Correct 4 ms 4956 KB Output is correct
17 Correct 54 ms 4948 KB Output is correct
18 Correct 4 ms 4956 KB Output is correct
19 Execution timed out 3080 ms 10636 KB Time limit exceeded
20 Halted 0 ms 0 KB -