oj.uz

Submission #964442

# Submission time Handle Problem Language Result Execution time Memory
964442 2024-04-16T22:14:15 Z Unforgettablepl Examination (JOI19_examination) C++17
0 / 100
 99 ms 11320 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;

#define int long long

struct fenwick{
    int n;vector<int> tree;
    fenwick(int n):n(n+1),tree(n+2){}
    int get(int x){
        int ans = 0;
        x++;
        while(x){
            ans+=tree[x];
            x-=x&-x;
        }
        return ans;
    }
    void add(int x){
        x++;
        while(x<=n){
            tree[x]++;
            x+=x&-x;
        }
    }
};

int ans[100001];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> students1;
    vector<tuple<int,int,int>> students2;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        students1.emplace_back(x,y);
        students2.emplace_back(x+y,x,y);
    }
    vector<tuple<int,int,int>> queries1;
    vector<tuple<int,int,int,int>> queries2;
    for(int i=1;i<=q;i++){
        int a,b,c;cin>>a>>b>>c;
        if(a+b>=c)queries1.emplace_back(a,b,i);
        else queries2.emplace_back(c,a,b,i);
    }
    sort(queries1.rbegin(),queries1.rend());
    sort(queries2.rbegin(),queries2.rend());
    sort(students1.rbegin(),students1.rend());
    sort(students2.rbegin(),students2.rend());
    auto iter = students1.begin();
    orderedset f1;
    orderedset f2;
    int curradded = 0;
    for(auto[a,b,idx]:queries1){
        while(iter!=students1.end() and iter->first>=a){
            f1.insert(iter->second);
            iter++;
            curradded++;
        }
        ans[idx] = curradded-f1.order_of_key(b-1);
    }
    f1.clear();
    auto iter2 = students2.begin();
    curradded=0;
    for(auto[c,a,b,idx]:queries2){
        while(iter2!=students2.end() and get<0>(*iter2)>=c){
            f1.insert(get<1>(*iter2));
            f2.insert(get<2>(*iter2));
            iter2++;
            curradded++;
        }
        ans[idx] = curradded-f1.order_of_key(a-1)-f2.order_of_key(b-1);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Subtask #1
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 0 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 1 ms 348 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 4 ms 1148 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Incorrect 3 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 11320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 11320 KB Output isn't correct
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 0 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 1 ms 348 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 4 ms 1148 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Incorrect 3 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -