oj.uz

Submission #418003

# Submission time Handle Problem Language Result Execution time Memory
418003 2021-06-04T20:46:07 Z Runtime_error_ Examination (JOI19_examination) C++14
0 / 100
 1896 ms 152188 KB 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ll long long
#define mid (l+r)/2
#define le node+node
#define ri node+node+1
#define pb push_back
#define mp make_pair
using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
 ordered_set;

const int inf = 2e5+9;
int n,q,Math[inf],Info[inf],qx[inf],qy[inf],qz[inf],qans[inf];
vector<pair<int,int>> events;

int cnt;
map<int,int> compress;

ordered_set st[inf<<2];

void update(int node,int l,int r,int idx,int val){
    st[node].insert(val);
    if(l == r)
        return ;
    if(idx <= mid)
        update(le,l,mid,idx,val);
    else
        update(ri,mid+1,r,idx,val);
}

int query(int node,int l,int r,int x,int y,int val){
    if(l>r || r<x || l>y || x>y || st[node].empty())
        return 0;
    if(l>=x && r<=y)
        return st[node].size()- st[node].order_of_key(val-1);

    return query(le,l,mid,x,y,val) + query(ri,mid+1,r,x,y,val);
}

int main(){

    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d%d",Math+i,Info+i),
        events.pb( mp( Math[i]+Info[i],i ) ),compress[Math[i]] = 1;

    for(int i=1;i<=q;i++){
        scanf("%d%d%d",qx+i,qy+i,qz+i);
        compress[qx[i]] = 1;
        events.pb( mp( qz[i],-i ) );
    }

    for(auto &o:compress)
        o.second = ++cnt;
    for(int i=1;i<=n;i++)
        Math[i] = compress[ Math[i] ];
    for(int i=1;i<=q;i++)
        qx[i] = compress[ qx[i] ];
    sort(rall(events));
    for(auto o:events){
        int i = o.second;
        if(i<0)//query
            i = -i,qans[i] = query(1,1,cnt,qx[i],cnt,qy[i]);
        else
            update(1,1,cnt,Math[i],Info[i]);
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",qans[i]);
}
/*
5 1
35 100
70 70
45 15
80 40
20 95
60 60 80

*/

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]
   55 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
examination.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d",Math+i,Info+i),
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d%d",qx+i,qy+i,qz+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62936 KB Output is correct
2 Correct 56 ms 62860 KB Output is correct
3 Correct 57 ms 62924 KB Output is correct
4 Correct 58 ms 62848 KB Output is correct
5 Correct 58 ms 62920 KB Output is correct
6 Correct 57 ms 62920 KB Output is correct
7 Correct 85 ms 65356 KB Output is correct
8 Correct 85 ms 65416 KB Output is correct
9 Correct 84 ms 65348 KB Output is correct
10 Incorrect 79 ms 64244 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1896 ms 152188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1896 ms 152188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62936 KB Output is correct
2 Correct 56 ms 62860 KB Output is correct
3 Correct 57 ms 62924 KB Output is correct
4 Correct 58 ms 62848 KB Output is correct
5 Correct 58 ms 62920 KB Output is correct
6 Correct 57 ms 62920 KB Output is correct
7 Correct 85 ms 65356 KB Output is correct
8 Correct 85 ms 65416 KB Output is correct
9 Correct 84 ms 65348 KB Output is correct
10 Incorrect 79 ms 64244 KB Output isn't correct
11 Halted 0 ms 0 KB -