oj.uz

Submission #126918

# Submission time Handle Problem Language Result Execution time Memory
126918 2019-07-08T15:43:12 Z zoooma13 Examination (JOI19_examination) C++14
43 / 100
 2279 ms 133416 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MAX_N 100005
#define FL (p<<1)|1
#define FR (p<<1)+2
#define all(v) (v).begin() ,(v).end()

struct cont{
    int a ,b ,c ,idx;
    bool operator<(const cont&rhs){
        return c < rhs.c;
    }
};

vector <int> comp;
int smlr(int num){
    return lower_bound(comp.begin() ,comp.end() ,num)-comp.begin();
}

int n ,q;
vector <cont> stds;
vector <cont> qs;
vector <int> pnts[3*MAX_N];

ordered_set <int> stree[4*MAX_N];
void bld(int l=0 ,int r=comp.size() ,int p=0)
{
    if(l == r){
        for(int&v : pnts[l])
            stree[p].insert(v);
        return;
    }

    int mid = (l+r)>>1;
    bld(l ,mid ,FL);
    bld(mid+1 ,r ,FR);
    for(auto&i : stree[FL])
        stree[p].insert(i);
    for(auto&i : stree[FR])
        stree[p].insert(i);
}
int qry(int ql ,int v ,int l=0 ,int r=comp.size() ,int p=0)
{
    if(ql <= l)
        return stree[p].size()-stree[p].order_of_key(v);
    if(r < ql)
        return 0;

    int mid = (l+r)>>1;
    return qry(ql ,v ,l ,mid ,FL) + qry(ql ,v ,mid+1 ,r ,FR);
}
void rem(int id ,int va ,int l=0 ,int r=comp.size() ,int p=0)
{
    stree[p].erase(stree[p].find_by_order(stree[p].order_of_key(va)));
    if(l == r)
        return;

    int mid = (l+r)>>1;
    if(id <= mid) rem(id ,va ,l ,mid ,FL);
    else          rem(id ,va ,mid+1 ,r ,FR);
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int s,t,i=0; i<n; i++){
        scanf("%d%d",&s,&t);
        stds.push_back({s ,t ,s+t ,i});
        comp.push_back(s);
        comp.push_back(t);
        comp.push_back(s+t);
    }

    sort(comp.begin() ,comp.end());
    comp.resize(unique(comp.begin() ,comp.end())-comp.begin());

    for(auto&s : stds){
        s.a = smlr(s.a);
        s.b = smlr(s.b);
        s.c = smlr(s.c);
        pnts[s.a].push_back(s.b);
    }

    for(int a,b,c,i=0; i<q; i++){
        scanf("%d%d%d",&a,&b,&c);
        a = smlr(a);
        b = smlr(b);
        c = smlr(c);
        qs.push_back({a ,b ,c ,i});
    }

    sort(stds.begin() ,stds.end());
    sort(qs.begin() ,qs.end());

    bld();

    vector <int> ans(q);
    int st_ptr = 0;
    for(cont&q : qs){
        while(st_ptr < n && stds[st_ptr].c < q.c){
            rem(stds[st_ptr].a ,stds[st_ptr].b);
            st_ptr++;
        }

        ans[q.idx] = qry(q.a ,q.b);
    }

    for(int&i : ans)
        printf("%d\n",i);
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:72: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:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&s,&t);
         ~~~~~^~~~~~~~~~~~~~
examination.cpp:92: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 52 ms 38648 KB Output is correct
2 Correct 52 ms 38648 KB Output is correct
3 Correct 53 ms 38776 KB Output is correct
4 Correct 52 ms 38732 KB Output is correct
5 Correct 61 ms 38652 KB Output is correct
6 Correct 52 ms 38648 KB Output is correct
7 Correct 84 ms 41004 KB Output is correct
8 Correct 81 ms 40924 KB Output is correct
9 Correct 83 ms 40924 KB Output is correct
10 Correct 78 ms 40952 KB Output is correct
11 Correct 77 ms 40860 KB Output is correct
12 Correct 68 ms 39652 KB Output is correct
13 Correct 74 ms 40952 KB Output is correct
14 Correct 75 ms 41080 KB Output is correct
15 Correct 74 ms 40952 KB Output is correct
16 Correct 74 ms 40824 KB Output is correct
17 Correct 72 ms 40824 KB Output is correct
18 Correct 60 ms 39160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 130332 KB Output is correct
2 Correct 1358 ms 130452 KB Output is correct
3 Correct 1243 ms 130432 KB Output is correct
4 Correct 1115 ms 127872 KB Output is correct
5 Correct 1245 ms 126872 KB Output is correct
6 Correct 473 ms 70524 KB Output is correct
7 Correct 1090 ms 130428 KB Output is correct
8 Correct 988 ms 130436 KB Output is correct
9 Correct 958 ms 130432 KB Output is correct
10 Correct 1180 ms 124204 KB Output is correct
11 Correct 934 ms 125668 KB Output is correct
12 Correct 231 ms 53476 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 130332 KB Output is correct
2 Correct 1358 ms 130452 KB Output is correct
3 Correct 1243 ms 130432 KB Output is correct
4 Correct 1115 ms 127872 KB Output is correct
5 Correct 1245 ms 126872 KB Output is correct
6 Correct 473 ms 70524 KB Output is correct
7 Correct 1090 ms 130428 KB Output is correct
8 Correct 988 ms 130436 KB Output is correct
9 Correct 958 ms 130432 KB Output is correct
10 Correct 1180 ms 124204 KB Output is correct
11 Correct 934 ms 125668 KB Output is correct
12 Correct 231 ms 53476 KB Output is correct
13 Correct 2279 ms 130420 KB Output is correct
14 Correct 1915 ms 133232 KB Output is correct
15 Correct 1272 ms 132968 KB Output is correct
16 Correct 1602 ms 130148 KB Output is correct
17 Correct 1982 ms 129156 KB Output is correct
18 Correct 543 ms 71656 KB Output is correct
19 Correct 2246 ms 133416 KB Output is correct
20 Correct 2236 ms 133216 KB Output is correct
21 Correct 2132 ms 133376 KB Output is correct
22 Correct 1184 ms 126036 KB Output is correct
23 Correct 919 ms 127156 KB Output is correct
24 Correct 233 ms 54408 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 38648 KB Output is correct
2 Correct 52 ms 38648 KB Output is correct
3 Correct 53 ms 38776 KB Output is correct
4 Correct 52 ms 38732 KB Output is correct
5 Correct 61 ms 38652 KB Output is correct
6 Correct 52 ms 38648 KB Output is correct
7 Correct 84 ms 41004 KB Output is correct
8 Correct 81 ms 40924 KB Output is correct
9 Correct 83 ms 40924 KB Output is correct
10 Correct 78 ms 40952 KB Output is correct
11 Correct 77 ms 40860 KB Output is correct
12 Correct 68 ms 39652 KB Output is correct
13 Correct 74 ms 40952 KB Output is correct
14 Correct 75 ms 41080 KB Output is correct
15 Correct 74 ms 40952 KB Output is correct
16 Correct 74 ms 40824 KB Output is correct
17 Correct 72 ms 40824 KB Output is correct
18 Correct 60 ms 39160 KB Output is correct
19 Correct 1259 ms 130332 KB Output is correct
20 Correct 1358 ms 130452 KB Output is correct
21 Correct 1243 ms 130432 KB Output is correct
22 Correct 1115 ms 127872 KB Output is correct
23 Correct 1245 ms 126872 KB Output is correct
24 Correct 473 ms 70524 KB Output is correct
25 Correct 1090 ms 130428 KB Output is correct
26 Correct 988 ms 130436 KB Output is correct
27 Correct 958 ms 130432 KB Output is correct
28 Correct 1180 ms 124204 KB Output is correct
29 Correct 934 ms 125668 KB Output is correct
30 Correct 231 ms 53476 KB Output is correct
31 Correct 2279 ms 130420 KB Output is correct
32 Correct 1915 ms 133232 KB Output is correct
33 Correct 1272 ms 132968 KB Output is correct
34 Correct 1602 ms 130148 KB Output is correct
35 Correct 1982 ms 129156 KB Output is correct
36 Correct 543 ms 71656 KB Output is correct
37 Correct 2246 ms 133416 KB Output is correct
38 Correct 2236 ms 133216 KB Output is correct
39 Correct 2132 ms 133376 KB Output is correct
40 Correct 1184 ms 126036 KB Output is correct
41 Correct 919 ms 127156 KB Output is correct
42 Correct 233 ms 54408 KB Output is correct
43 Runtime error 366 ms 97056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -