oj.uz

Submission #171000

# Submission time Handle Problem Language Result Execution time Memory
171000 2019-12-27T02:06:47 Z errorgorn Examination (JOI19_examination) C++14
100 / 100
 768 ms 264052 KB 
#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

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);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 22 ms 11000 KB Output is correct
8 Correct 22 ms 11000 KB Output is correct
9 Correct 22 ms 11000 KB Output is correct
10 Correct 14 ms 5752 KB Output is correct
11 Correct 13 ms 5752 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 22 ms 11000 KB Output is correct
14 Correct 23 ms 11000 KB Output is correct
15 Correct 22 ms 11128 KB Output is correct
16 Correct 13 ms 5752 KB Output is correct
17 Correct 13 ms 5756 KB Output is correct
18 Correct 5 ms 632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 26788 KB Output is correct
2 Correct 300 ms 26896 KB Output is correct
3 Correct 323 ms 26996 KB Output is correct
4 Correct 149 ms 17252 KB Output is correct
5 Correct 151 ms 17280 KB Output is correct
6 Correct 110 ms 7784 KB Output is correct
7 Correct 275 ms 26728 KB Output is correct
8 Correct 284 ms 26724 KB Output is correct
9 Correct 249 ms 26596 KB Output is correct
10 Correct 146 ms 17128 KB Output is correct
11 Correct 145 ms 17128 KB Output is correct
12 Correct 88 ms 7400 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 26788 KB Output is correct
2 Correct 300 ms 26896 KB Output is correct
3 Correct 323 ms 26996 KB Output is correct
4 Correct 149 ms 17252 KB Output is correct
5 Correct 151 ms 17280 KB Output is correct
6 Correct 110 ms 7784 KB Output is correct
7 Correct 275 ms 26728 KB Output is correct
8 Correct 284 ms 26724 KB Output is correct
9 Correct 249 ms 26596 KB Output is correct
10 Correct 146 ms 17128 KB Output is correct
11 Correct 145 ms 17128 KB Output is correct
12 Correct 88 ms 7400 KB Output is correct
13 Correct 283 ms 27196 KB Output is correct
14 Correct 290 ms 27208 KB Output is correct
15 Correct 336 ms 26724 KB Output is correct
16 Correct 153 ms 17672 KB Output is correct
17 Correct 240 ms 17512 KB Output is correct
18 Correct 113 ms 7780 KB Output is correct
19 Correct 290 ms 27180 KB Output is correct
20 Correct 302 ms 27148 KB Output is correct
21 Correct 279 ms 27112 KB Output is correct
22 Correct 146 ms 17140 KB Output is correct
23 Correct 146 ms 17004 KB Output is correct
24 Correct 89 ms 7396 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 22 ms 11000 KB Output is correct
8 Correct 22 ms 11000 KB Output is correct
9 Correct 22 ms 11000 KB Output is correct
10 Correct 14 ms 5752 KB Output is correct
11 Correct 13 ms 5752 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 22 ms 11000 KB Output is correct
14 Correct 23 ms 11000 KB Output is correct
15 Correct 22 ms 11128 KB Output is correct
16 Correct 13 ms 5752 KB Output is correct
17 Correct 13 ms 5756 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 335 ms 26788 KB Output is correct
20 Correct 300 ms 26896 KB Output is correct
21 Correct 323 ms 26996 KB Output is correct
22 Correct 149 ms 17252 KB Output is correct
23 Correct 151 ms 17280 KB Output is correct
24 Correct 110 ms 7784 KB Output is correct
25 Correct 275 ms 26728 KB Output is correct
26 Correct 284 ms 26724 KB Output is correct
27 Correct 249 ms 26596 KB Output is correct
28 Correct 146 ms 17128 KB Output is correct
29 Correct 145 ms 17128 KB Output is correct
30 Correct 88 ms 7400 KB Output is correct
31 Correct 283 ms 27196 KB Output is correct
32 Correct 290 ms 27208 KB Output is correct
33 Correct 336 ms 26724 KB Output is correct
34 Correct 153 ms 17672 KB Output is correct
35 Correct 240 ms 17512 KB Output is correct
36 Correct 113 ms 7780 KB Output is correct
37 Correct 290 ms 27180 KB Output is correct
38 Correct 302 ms 27148 KB Output is correct
39 Correct 279 ms 27112 KB Output is correct
40 Correct 146 ms 17140 KB Output is correct
41 Correct 146 ms 17004 KB Output is correct
42 Correct 89 ms 7396 KB Output is correct
43 Correct 724 ms 263768 KB Output is correct
44 Correct 733 ms 264052 KB Output is correct
45 Correct 768 ms 264044 KB Output is correct
46 Correct 334 ms 135908 KB Output is correct
47 Correct 331 ms 135784 KB Output is correct
48 Correct 104 ms 7656 KB Output is correct
49 Correct 764 ms 263940 KB Output is correct
50 Correct 724 ms 263864 KB Output is correct
51 Correct 730 ms 263756 KB Output is correct
52 Correct 331 ms 135904 KB Output is correct
53 Correct 323 ms 135268 KB Output is correct