oj.uz

Submission #897226

# Submission time Handle Problem Language Result Execution time Memory
897226 2024-01-02T18:36:43 Z MarwenElarbi Examination (JOI19_examination) C++17
2 / 100
 24 ms 13852 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9;
const int nax = 1e5+5;
const int lg = 20;
struct student{
    int sum, left, right;
};
int n,q;
vector<student> tab(nax);
vector<int> segtree[nax][2];
int bs(int cur){
    int l=-1;
    int r=n;
    while(r-l>1){
        int mid=(r+l)/2;
        if(tab[mid].sum>=cur) r=mid;
        else l=mid;
    }
    return r;
}
void build(int pos,int l,int r,int idx){
    if(l==r){
        if(idx==0) segtree[pos][idx].pb(tab[l].left);
        else segtree[pos][idx].pb(tab[l].right);
        return;
    }
    int mid=(l+r)/2;
    build(pos*2+1,l,mid,idx);
    build(pos*2+2,mid+1,r,idx);
    int j=0;
    for (int i = 0; i < segtree[pos*2+1][idx].size(); ++i)
    {
        while(j<segtree[pos*2+2][idx].size()&&segtree[pos*2+2][idx][j]<segtree[pos*2+1][idx][i]) segtree[pos][idx].pb(segtree[pos*2+2][idx][j++]);
        segtree[pos][idx].pb(segtree[pos*2+1][idx][i]);
    }
    while(j<segtree[pos*2+2][idx].size()) segtree[pos][idx].pb(segtree[pos*2+2][idx][j++]);
    return;
}
int query(int pos,int l,int r,int left,int right,int idx,int value){
    if(l>r||l>right||r<left) return 0;
    if(l>=left&&r<=right){
        int lefty=-1;
        int righty=segtree[pos][idx].size();
        while(righty-lefty>1){
            int middle=(lefty+righty)/2;
            //cout <<segtree[pos][idx][middle]<<endl;
            if(segtree[pos][idx][middle]<value) lefty=middle;
            else righty=middle;
        }
        //cout <<l<<" "<<r<<" "<<lefty<<endl;
        return lefty+1;
    }
    int mid=(r+l)/2;
    return query(pos*2+1,l,mid,left,right,idx,value)+query(pos*2+2,mid+1,r,left,right,idx,value);
}
int main() {
    optimise;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    cin>>n>>q;
    tab.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i].left>>tab[i].right;
        tab[i].sum=tab[i].left+tab[i].right;
    }
    auto cmp=[&](student a,student b){
        return a.sum<b.sum;
    };
    sort(tab.begin(),tab.end(),cmp);
    build(0,0,n-1,0);
    build(0,0,n-1,1);
    /*for (int i = 0; i < tab.size(); ++i)
    {
        cout<<tab[i].sum<<" "<<tab[i].left<<" "<<tab[i].right<<endl;
    }*/
    while(q--){
        int a,b,c;
        cin>>a>>b>>c;
        int idx=bs(max(c,a+b));
        if(idx==n){
            cout << 0<<endl;
            continue;
        }
        int x=query(0,0,n-1,idx,n-1,0,a)+query(0,0,n-1,idx,n-1,1,b);
        //cout <<idx<<" "<<x<<endl;
        cout << n-idx-x<<endl;
    }
}

Compilation message

examination.cpp: In function 'void build(int, int, int, int)':
examination.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < segtree[pos*2+1][idx].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(j<segtree[pos*2+2][idx].size()&&segtree[pos*2+2][idx][j]<segtree[pos*2+1][idx][i]) segtree[pos][idx].pb(segtree[pos*2+2][idx][j++]);
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while(j<segtree[pos*2+2][idx].size()) segtree[pos][idx].pb(segtree[pos*2+2][idx][j++]);
      |           ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6216 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 10 ms 7004 KB Output is correct
8 Correct 10 ms 7256 KB Output is correct
9 Correct 10 ms 7004 KB Output is correct
10 Correct 9 ms 6952 KB Output is correct
11 Correct 11 ms 7004 KB Output is correct
12 Correct 10 ms 7056 KB Output is correct
13 Correct 12 ms 7004 KB Output is correct
14 Correct 10 ms 7000 KB Output is correct
15 Correct 10 ms 7004 KB Output is correct
16 Correct 9 ms 7004 KB Output is correct
17 Correct 9 ms 6988 KB Output is correct
18 Correct 7 ms 7004 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 13852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 13852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6216 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 10 ms 7004 KB Output is correct
8 Correct 10 ms 7256 KB Output is correct
9 Correct 10 ms 7004 KB Output is correct
10 Correct 9 ms 6952 KB Output is correct
11 Correct 11 ms 7004 KB Output is correct
12 Correct 10 ms 7056 KB Output is correct
13 Correct 12 ms 7004 KB Output is correct
14 Correct 10 ms 7000 KB Output is correct
15 Correct 10 ms 7004 KB Output is correct
16 Correct 9 ms 7004 KB Output is correct
17 Correct 9 ms 6988 KB Output is correct
18 Correct 7 ms 7004 KB Output is correct
19 Runtime error 24 ms 13852 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -