oj.uz

Submission #945412

# Submission time Handle Problem Language Result Execution time Memory
945412 2024-03-13T18:22:23 Z JakobZorz Examination (JOI19_examination) C++17
2 / 100
 3000 ms 15112 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

struct Obj{
    ll a,b,c;
    int res;
    bool is_q;
};

bool cmp1(Obj*a,Obj*b){
    return a->c<b->c;
}

bool cmp2(Obj*a,Obj*b){
    return a->b<b->b;
}

void proc(vector<Obj*>vals,vector<Obj*>qrs){
    sort(vals.begin(),vals.end(),cmp2);
    reverse(vals.begin(),vals.end());
    sort(qrs.begin(),qrs.end(),cmp2);
    reverse(qrs.begin(),qrs.end());
    int i=0;
    for(auto qr:qrs){
        while(i<(int)vals.size()&&vals[i]->b>=qr->b)
            i++;
        for(int j=0;j<i;j++)
            qr->res+=vals[j]->a>=qr->a;
    }
}

void dc(vector<Obj*>arr){
    int n=(int)arr.size();
    if(arr[0]->c==arr.back()->c){
        vector<Obj*>qrs,vals;
        for(int i=0;i<n;i++){
            if(arr[i]->is_q)
                qrs.push_back(arr[i]);
            else
                vals.push_back(arr[i]);
        }
        proc(vals,qrs);
        return;
    }
    int mid=0;
    for(int i=0;i<n/2||mid==0;i++)
        if(arr[i]->c!=arr[i+1]->c)
            mid=i+1;
    vector<Obj*>qrs,vals;
    vector<Obj*>arr1,arr2;
    for(int i=mid;i<n;i++){
        arr2.push_back(arr[i]);
        if(!arr[i]->is_q)
            vals.push_back(arr[i]);
    }
    for(int i=0;i<mid;i++){
        arr1.push_back(arr[i]);
        if(arr[i]->is_q)
            qrs.push_back(arr[i]);
    }
    proc(vals,qrs);
    dc(arr1);
    dc(arr2);
}

void solve(){
    int n,q;
    cin>>n>>q;
    vector<Obj>arr(n);
    for(Obj&i:arr){
        cin>>i.a>>i.b;
        i.c=i.a+i.b;
        i.is_q=false;
        i.res=0;
    }
    vector<Obj>qrs(q);
    for(Obj&i:qrs){
        cin>>i.a>>i.b>>i.c;
        i.is_q=true;
        i.res=0;
    }
    vector<Obj*>all;
    for(Obj&i:arr)
        all.push_back(&i);
    for(Obj&i:qrs)
        all.push_back(&i);
    sort(all.begin(),all.end(),cmp1);
    dc(all);
    for(auto i:qrs)
        cout<<i.res<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("/Users/jakob/cp_testing/test.txt","r",stdin);//freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}


/*

5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
 
 */

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 8 ms 860 KB Output is correct
8 Correct 9 ms 860 KB Output is correct
9 Correct 9 ms 860 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 10 ms 860 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 8 ms 860 KB Output is correct
14 Correct 8 ms 860 KB Output is correct
15 Correct 7 ms 860 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 7 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 15112 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 15112 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 344 KB Output is correct
2 Correct 1 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 8 ms 860 KB Output is correct
8 Correct 9 ms 860 KB Output is correct
9 Correct 9 ms 860 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 10 ms 860 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 8 ms 860 KB Output is correct
14 Correct 8 ms 860 KB Output is correct
15 Correct 7 ms 860 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 7 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Execution timed out 3055 ms 15112 KB Time limit exceeded
20 Halted 0 ms 0 KB -