제출 #897226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897226		MarwenElarbi	Examination (JOI19_examination)	C++17	2 / 100	24 ms	13852 KiB

examination

#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;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57