oj.uz

Submission #991552

# Submission time Handle Problem Language Result Execution time Memory
991552 2024-06-02T12:13:13 Z vladilius Examination (JOI19_examination) C++17
2 / 100
 3000 ms 16848 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int inf = 2e9 + 5;

struct OS{
    vector<int> a;
    void add(int x){
        a.pb(x);
    }
    int get(int x){
        int out = 0;
        for (int i: a) out += (i < x);
        return out;
    }
    void clear(){
        a.clear();
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    struct data{
        int x, y, z, i;
    };
    
    auto cmp = [&](data& a, data& b){
        return a.x < b.x;
    };
    
    int n, q; cin>>n>>q;
    vector<pii> t(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>t[i].ff>>t[i].ss;
    }
    sort(t.begin() + 1, t.end());
    
    vector<data> qs(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>qs[i].x>>qs[i].y>>qs[i].z;
        qs[i].i = i;
    }
    sort(qs.begin() + 1, qs.end(), cmp);
    vector<data> all = {{}};
    
    int j = n, cur = 1;
    for (int i = q; i > 0; i--){
        while (j > 0 && t[j].ff >= qs[i].x){
            all.pb({cur++, t[j].ss, t[j].ff + t[j].ss, 0});
            // cout<<t[j].ss<<" "<<t[j].ff + t[j].ss<<"\n";
            j--;
        }
        // cout<<qs[i].y<<" "<<qs[i].z<<"\n";
        all.pb({cur, inf, inf, qs[i].i});
        all.pb({cur, qs[i].y, inf, -qs[i].i});
        all.pb({cur, inf, qs[i].z, -qs[i].i});
        all.pb({cur++, qs[i].y, qs[i].z, qs[i].i});
    }
    sort(all.begin() + 1, all.end(), cmp);
    
    vector<int> out(q + 1), cnt(all.size());
    OS T;
    function<void(int, int)> solve = [&](int l, int r){
        if (l == r) return;
        int m = (l + r) / 2;
        solve(l, m);
        solve(m + 1, r);
        
        vector<data> arr;
        for (int i = l; i <= m; i++){
            if (all[i].i == 0) arr.pb({all[i].y, all[i].z, 0, 0});
        }
        for (int i = m + 1; i <= r; i++){
            if (all[i].i != 0) arr.pb({all[i].y, all[i].z, 0, i});
        }
        sort(arr.begin(), arr.end(), cmp);
        int i = 0, j = 0;
        while (i < arr.size()){
            while (j < arr.size() && arr[j].x < arr[i].x){
                if (arr[j].i == 0) T.add(arr[j].y);
                j++;
            }
            if (arr[i].i) cnt[arr[i].i] += T.get(arr[i].y);
            i++;
        }
        T.clear();
    };
    solve(1, (int) all.size() - 1);
    for (int i = 1; i < all.size(); i++){
        if (all[i].i == 0) continue;
        out[abs(all[i].i)] += (2 * (all[i].i > 0) - 1) * cnt[i];
    }
    for (int i = 1; i <= q; i++){
        cout<<out[i]<<"\n";
    }
}

Compilation message

examination.cpp: In lambda function:
examination.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         while (i < arr.size()){
      |                ~~^~~~~~~~~~~~
examination.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             while (j < arr.size() && arr[j].x < arr[i].x){
      |                    ~~^~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 1; i < all.size(); i++){
      |                     ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 15 ms 984 KB Output is correct
8 Correct 17 ms 984 KB Output is correct
9 Correct 16 ms 984 KB Output is correct
10 Correct 15 ms 980 KB Output is correct
11 Correct 16 ms 984 KB Output is correct
12 Correct 16 ms 984 KB Output is correct
13 Correct 15 ms 992 KB Output is correct
14 Correct 16 ms 1120 KB Output is correct
15 Correct 15 ms 984 KB Output is correct
16 Correct 14 ms 1184 KB Output is correct
17 Correct 15 ms 984 KB Output is correct
18 Correct 9 ms 980 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 16848 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 3055 ms 16848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 15 ms 984 KB Output is correct
8 Correct 17 ms 984 KB Output is correct
9 Correct 16 ms 984 KB Output is correct
10 Correct 15 ms 980 KB Output is correct
11 Correct 16 ms 984 KB Output is correct
12 Correct 16 ms 984 KB Output is correct
13 Correct 15 ms 992 KB Output is correct
14 Correct 16 ms 1120 KB Output is correct
15 Correct 15 ms 984 KB Output is correct
16 Correct 14 ms 1184 KB Output is correct
17 Correct 15 ms 984 KB Output is correct
18 Correct 9 ms 980 KB Output is correct
19 Execution timed out 3055 ms 16848 KB Time limit exceeded
20 Halted 0 ms 0 KB -