oj.uz

Submission #205172

# Submission time Handle Problem Language Result Execution time Memory
205172 2020-02-28T08:50:09 Z egekabas Examination (JOI19_examination) C++14
100 / 100
 1045 ms 71696 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
struct query{
    ll x, y, z, id;
};
struct st{
    ll a, b, id;
};
query qs[100009];
ll n, q;
st sa[100009];
st sb[100009];
ll idplace[100009];
ll sortbya(st x, st y){return x.a < y.a;}
ll sortbyb(st x, st y){return x.b < y.b;}
vector<ll> compress;
ll getid(ll x){return lower_bound(compress.begin(), compress.end(), x)-compress.begin();}
vector<ll> seg[400009];
vector<ll> bit[400009];
ll build(ll v, ll tl, ll tr){
    seg[v].pb(-1);
    if(tl == tr)
        seg[v].pb(getid(sb[tl].a+sb[tl].b));
    else{
        ll tm = (tl+tr)/2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        seg[v].resize(seg[2*v].size()+seg[2*v+1].size()-1);
        merge(seg[2*v].begin()+1, seg[2*v].end(), seg[2*v+1].begin()+1, seg[2*v+1].end(), seg[v].begin()+1);
    //cout << seg[2*v].size() << ' ' << seg[2*v+1].size() << ' ' << seg[v].size() << '\n';
    }
    bit[v].resize(seg[v].size());
}
ll getbit(ll id, vector<ll> &v){
    ll ret = 0;
    for(;id < v.size(); id += id&(-id))
        ret += v[id];
    return ret;
}
ll updbit(ll id, ll val, vector<ll> &v){
    for(;id > 0; id -= id&(-id))
        v[id] += val;
}
void upd(ll v, ll tl, ll tr, ll id, ll val){
    ll place = lower_bound(seg[v].begin(), seg[v].end(), val)-seg[v].begin();
    updbit(place, 1, bit[v]);
    if(tl != tr){
        ll tm = (tl+tr)/2;
        if(id <= tm)
            upd(2*v, tl, tm, id, val);
        else
            upd(2*v+1, tm+1, tr, id, val);
    }
}
ll get(ll v, ll tl, ll tr, ll l, ll r, ll val){
    if(tr < l || r < tl || l > r)
        return 0;
    if(l <= tl && tr <= r){
        ll place = lower_bound(seg[v].begin(), seg[v].end(), val)-seg[v].begin();    
        
        return getbit(place, bit[v]);
    }
    else{
        ll tm = (tl+tr)/2;
        return get(2*v, tl, tm, l, r, val)+get(2*v+1, tm+1, tr, l, r, val);
    }
}
ll ans[100009];
ll sortquery(query a, query b){return a.x > b.x;}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q;
    for(ll i = 0; i < n; ++i){
        cin >> sa[i].a >> sa[i].b;
        compress.pb(sa[i].a+sa[i].b);
        sa[i].id = i;
        sb[i] = sa[i];
    }
    sort(sa, sa+n, sortbya);
    sort(sb, sb+n, sortbyb);
    for(ll i = 0; i < n; ++i)
        idplace[sb[i].id] = i;
    for(ll i = 0; i < q; ++i){
        cin >> qs[i].x >> qs[i].y >> qs[i].z;
        compress.pb(qs[i].z);
        qs[i].id = i; 
    }
    sort(qs, qs+n, sortquery);
    sort(compress.begin(), compress.end());
    compress.resize(unique(compress.begin(), compress.end())-compress.begin());
    build(1, 0, n-1);
    ll cura = n-1;
    for(ll i = 0; i < q; ++i){
        while(cura >= 0 && sa[cura].a >= qs[i].x){
            upd(1, 0, n-1, idplace[sa[cura].id], getid(sa[cura].a+sa[cura].b));
            --cura;
        }
        ll l = 0, r = n;
        while(l < r){
            ll mid = (l+r)/2;
            if(sb[mid].b >= qs[i].y)
                r = mid;
            else
                l = mid+1;
        }
        ans[qs[i].id] = get(1, 0, n-1, l, n-1, getid(qs[i].z));
    }
    for(ll i = 0; i < q; ++i)
        cout << ans[i] << '\n';
}

Compilation message

examination.cpp: In function 'll build(ll, ll, ll)':
examination.cpp:44:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
examination.cpp: In function 'll getbit(ll, std::vector<long long int>&)':
examination.cpp:47:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;id < v.size(); id += id&(-id))
          ~~~^~~~~~~~~~
examination.cpp: In function 'll updbit(ll, ll, std::vector<long long int>&)':
examination.cpp:54:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19192 KB Output is correct
2 Correct 18 ms 19192 KB Output is correct
3 Correct 18 ms 19196 KB Output is correct
4 Correct 18 ms 19192 KB Output is correct
5 Correct 18 ms 19192 KB Output is correct
6 Correct 18 ms 19192 KB Output is correct
7 Correct 36 ms 20472 KB Output is correct
8 Correct 32 ms 20472 KB Output is correct
9 Correct 32 ms 20472 KB Output is correct
10 Correct 28 ms 20472 KB Output is correct
11 Correct 30 ms 20472 KB Output is correct
12 Correct 30 ms 20344 KB Output is correct
13 Correct 29 ms 20472 KB Output is correct
14 Correct 27 ms 20476 KB Output is correct
15 Correct 28 ms 20472 KB Output is correct
16 Correct 27 ms 20472 KB Output is correct
17 Correct 43 ms 20472 KB Output is correct
18 Correct 24 ms 20344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 69660 KB Output is correct
2 Correct 846 ms 69372 KB Output is correct
3 Correct 855 ms 69328 KB Output is correct
4 Correct 567 ms 68628 KB Output is correct
5 Correct 818 ms 68848 KB Output is correct
6 Correct 427 ms 68108 KB Output is correct
7 Correct 780 ms 69200 KB Output is correct
8 Correct 752 ms 69328 KB Output is correct
9 Correct 673 ms 69352 KB Output is correct
10 Correct 814 ms 68588 KB Output is correct
11 Correct 495 ms 68424 KB Output is correct
12 Correct 230 ms 67508 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 69660 KB Output is correct
2 Correct 846 ms 69372 KB Output is correct
3 Correct 855 ms 69328 KB Output is correct
4 Correct 567 ms 68628 KB Output is correct
5 Correct 818 ms 68848 KB Output is correct
6 Correct 427 ms 68108 KB Output is correct
7 Correct 780 ms 69200 KB Output is correct
8 Correct 752 ms 69328 KB Output is correct
9 Correct 673 ms 69352 KB Output is correct
10 Correct 814 ms 68588 KB Output is correct
11 Correct 495 ms 68424 KB Output is correct
12 Correct 230 ms 67508 KB Output is correct
13 Correct 969 ms 69864 KB Output is correct
14 Correct 988 ms 69680 KB Output is correct
15 Correct 907 ms 69224 KB Output is correct
16 Correct 743 ms 68940 KB Output is correct
17 Correct 947 ms 68960 KB Output is correct
18 Correct 466 ms 68028 KB Output is correct
19 Correct 971 ms 69916 KB Output is correct
20 Correct 1045 ms 69736 KB Output is correct
21 Correct 981 ms 69732 KB Output is correct
22 Correct 927 ms 68364 KB Output is correct
23 Correct 509 ms 68492 KB Output is correct
24 Correct 236 ms 67432 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19192 KB Output is correct
2 Correct 18 ms 19192 KB Output is correct
3 Correct 18 ms 19196 KB Output is correct
4 Correct 18 ms 19192 KB Output is correct
5 Correct 18 ms 19192 KB Output is correct
6 Correct 18 ms 19192 KB Output is correct
7 Correct 36 ms 20472 KB Output is correct
8 Correct 32 ms 20472 KB Output is correct
9 Correct 32 ms 20472 KB Output is correct
10 Correct 28 ms 20472 KB Output is correct
11 Correct 30 ms 20472 KB Output is correct
12 Correct 30 ms 20344 KB Output is correct
13 Correct 29 ms 20472 KB Output is correct
14 Correct 27 ms 20476 KB Output is correct
15 Correct 28 ms 20472 KB Output is correct
16 Correct 27 ms 20472 KB Output is correct
17 Correct 43 ms 20472 KB Output is correct
18 Correct 24 ms 20344 KB Output is correct
19 Correct 969 ms 69660 KB Output is correct
20 Correct 846 ms 69372 KB Output is correct
21 Correct 855 ms 69328 KB Output is correct
22 Correct 567 ms 68628 KB Output is correct
23 Correct 818 ms 68848 KB Output is correct
24 Correct 427 ms 68108 KB Output is correct
25 Correct 780 ms 69200 KB Output is correct
26 Correct 752 ms 69328 KB Output is correct
27 Correct 673 ms 69352 KB Output is correct
28 Correct 814 ms 68588 KB Output is correct
29 Correct 495 ms 68424 KB Output is correct
30 Correct 230 ms 67508 KB Output is correct
31 Correct 969 ms 69864 KB Output is correct
32 Correct 988 ms 69680 KB Output is correct
33 Correct 907 ms 69224 KB Output is correct
34 Correct 743 ms 68940 KB Output is correct
35 Correct 947 ms 68960 KB Output is correct
36 Correct 466 ms 68028 KB Output is correct
37 Correct 971 ms 69916 KB Output is correct
38 Correct 1045 ms 69736 KB Output is correct
39 Correct 981 ms 69732 KB Output is correct
40 Correct 927 ms 68364 KB Output is correct
41 Correct 509 ms 68492 KB Output is correct
42 Correct 236 ms 67432 KB Output is correct
43 Correct 974 ms 71696 KB Output is correct
44 Correct 981 ms 71692 KB Output is correct
45 Correct 957 ms 71656 KB Output is correct
46 Correct 724 ms 70120 KB Output is correct
47 Correct 900 ms 70112 KB Output is correct
48 Correct 481 ms 67688 KB Output is correct
49 Correct 891 ms 71660 KB Output is correct
50 Correct 902 ms 71628 KB Output is correct
51 Correct 828 ms 71660 KB Output is correct
52 Correct 907 ms 69968 KB Output is correct
53 Correct 514 ms 69292 KB Output is correct