Submission #171000

#TimeUsernameProblemLanguageResultExecution timeMemory
171000errorgornExamination (JOI19_examination)C++14
100 / 100
768 ms264052 KiB
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> ii;
const int MAX=1000000005;
struct grade{
    int index;
    int math,io;
    int total;
    grade (int _index,int _math,int _io, int _total){
        index=_index;
        math=_math;
        io=_io;
        total=_total;
    }
};
struct node{
    int s,e,m;
    int val;
    node *l,*r;
    bool split;
    node (int _s,int _e){
        s=_s,e=_e,m=(s+e)>>1;
        val=0;
        split=false;
    }
    void update(int i){
        if (s!=e){
            if (!split){
                split=true;
                l=new node(s,m);
                r=new node(m+1,e);
            }
            if (i<=m) l->update(i);
            else r->update(i);
        }
        val++;
    }
    int query(int i){
        if (e==i) return val;
        else if (!split) return val;
        else if (i<=m) return l->query(i);
        else return l->val+r->query(i);
    }
};
int n,q;
vector<ii> scores;
vector<grade> grades;
int ans[100005];
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&q);
    int a,b,c;
    for (int x=0;x<n;x++){
        scanf("%d%d",&a,&b);
        scores.push_back(ii(a,b));
    }
    for (int x=0;x<q;x++){
        scanf("%d%d%d",&a,&b,&c);
        grades.push_back(*new grade(x,a,b,max(c,a+b)));
    }
    sort(scores.begin(),scores.end(),[](ii i,ii j){return i.first+i.second<j.first+j.second;});
    sort(grades.begin(),grades.end(),[](grade &i,grade &j){return i.total<j.total;});
    grade *curr;
    node *math=new node(0,MAX), *io=new node(0,MAX);
    int added=0;
    while (!grades.empty()){
        curr=&grades.back(),grades.pop_back();
        while (!scores.empty() && scores.back().first+scores.back().second>=curr->total){
            added++;
            math->update(scores.back().first+1);
            io->update(scores.back().second+1);
            scores.pop_back();
        }
        ans[curr->index]=added-math->query(curr->math)-io->query(curr->io);
    }
    for (int x=0;x<q;x++) printf("%d\n",ans[x]);
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
examination.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
examination.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...