oj.uz

Submission #676418

# Submission time Handle Problem Language Result Execution time Memory
676418 2022-12-30T21:09:55 Z urosk Examination (JOI19_examination) C++14
43 / 100
 3000 ms 284772 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define maxn 400005
struct tupl{
    ll x,y,sum,id;
} v[maxn];
ll n,q;
pll a[maxn];
ordered_set t[4*maxn];
ll ls[4*maxn],rs[4*maxn],root,tsz;
void upd(ll v,ll tl,ll tr,ll i,ll x,bool f){
    if(f) t[v].insert(x);
    else t[v].erase(t[v].find_by_order(t[v].order_of_key(x)));
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(ls[v],tl,mid,i,x,f);
    else upd(rs[v],mid+1,tr,i,x,f);
}
ll get(ll v,ll tl,ll tr,ll l,ll r,ll x){
    if(r<tl||l>tr||tl>tr) return 0;
    if(l<=tl&&tr<=r){
        ll cnt = t[v].order_of_key(x);
        return sz(t[v]) - cnt;
    }
    ll mid = (tl+tr)/2;
    return get(ls[v],tl,mid,l,r,x) + get(rs[v],mid+1,tr,l,r,x);
}
void init(ll &v,ll tl,ll tr){
    v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
bool cmp(pll x,pll y){return x.fi+x.sc<y.fi+y.sc;}
bool cmp2(tupl x,tupl y){return x.sum<y.sum;}
map<ll,ll> mp;
set<ll> s;
ll it = 0;
ll ans[maxn];
void tc(){
    cin >> n >> q;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    for(ll i = 1;i<=q;i++) cin >> v[i].x >> v[i].y >> v[i].sum;
    for(ll i = 1;i<=q;i++) v[i].id = i;
    sort(a+1,a+1+n,cmp);
    sort(v+1,v+1+q,cmp2);
    for(ll i = 1;i<=n;i++) s.insert(a[i].fi),s.insert(a[i].sc);
    for(ll i = 1;i<=q;i++) s.insert(v[i].x),s.insert(v[i].y);
    for(ll x : s) mp[x] = ++it;
    init(root,1,it);
    for(ll i = 1;i<=n;i++) upd(root,1,it,mp[a[i].fi],mp[a[i].sc],1);
    ll k = 1;
    for(ll j = 1;j<=q;j++){
        while(k<=n&&a[k].fi+a[k].sc<v[j].sum){
            upd(root,1,it,mp[a[k].fi],mp[a[k].sc],0);
            k++;
        }
        ans[v[j].id] = get(root,1,it,mp[v[j].x],it,mp[v[j].y]);
    }
    for(ll i = 1;i<=q;i++) cout<<ans[i]<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 125476 KB Output is correct
2 Correct 92 ms 125592 KB Output is correct
3 Correct 90 ms 125644 KB Output is correct
4 Correct 90 ms 125640 KB Output is correct
5 Correct 92 ms 125504 KB Output is correct
6 Correct 91 ms 125512 KB Output is correct
7 Correct 116 ms 129428 KB Output is correct
8 Correct 117 ms 129496 KB Output is correct
9 Correct 115 ms 129472 KB Output is correct
10 Correct 111 ms 128460 KB Output is correct
11 Correct 111 ms 128588 KB Output is correct
12 Correct 100 ms 126440 KB Output is correct
13 Correct 112 ms 129644 KB Output is correct
14 Correct 110 ms 129592 KB Output is correct
15 Correct 112 ms 129612 KB Output is correct
16 Correct 105 ms 128736 KB Output is correct
17 Correct 106 ms 128528 KB Output is correct
18 Correct 96 ms 126140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2029 ms 228440 KB Output is correct
2 Correct 2060 ms 228516 KB Output is correct
3 Correct 2036 ms 228428 KB Output is correct
4 Correct 1232 ms 226012 KB Output is correct
5 Correct 1063 ms 226192 KB Output is correct
6 Correct 350 ms 152984 KB Output is correct
7 Correct 1675 ms 227980 KB Output is correct
8 Correct 1659 ms 227932 KB Output is correct
9 Correct 1455 ms 226284 KB Output is correct
10 Correct 1338 ms 228276 KB Output is correct
11 Correct 974 ms 225756 KB Output is correct
12 Correct 290 ms 145388 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2029 ms 228440 KB Output is correct
2 Correct 2060 ms 228516 KB Output is correct
3 Correct 2036 ms 228428 KB Output is correct
4 Correct 1232 ms 226012 KB Output is correct
5 Correct 1063 ms 226192 KB Output is correct
6 Correct 350 ms 152984 KB Output is correct
7 Correct 1675 ms 227980 KB Output is correct
8 Correct 1659 ms 227932 KB Output is correct
9 Correct 1455 ms 226284 KB Output is correct
10 Correct 1338 ms 228276 KB Output is correct
11 Correct 974 ms 225756 KB Output is correct
12 Correct 290 ms 145388 KB Output is correct
13 Correct 2537 ms 228320 KB Output is correct
14 Correct 2396 ms 231220 KB Output is correct
15 Correct 2037 ms 231104 KB Output is correct
16 Correct 1331 ms 228172 KB Output is correct
17 Correct 1104 ms 228252 KB Output is correct
18 Correct 374 ms 153912 KB Output is correct
19 Correct 2475 ms 231348 KB Output is correct
20 Correct 2513 ms 231404 KB Output is correct
21 Correct 2261 ms 230236 KB Output is correct
22 Correct 1367 ms 229924 KB Output is correct
23 Correct 975 ms 227508 KB Output is correct
24 Correct 279 ms 146380 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 125476 KB Output is correct
2 Correct 92 ms 125592 KB Output is correct
3 Correct 90 ms 125644 KB Output is correct
4 Correct 90 ms 125640 KB Output is correct
5 Correct 92 ms 125504 KB Output is correct
6 Correct 91 ms 125512 KB Output is correct
7 Correct 116 ms 129428 KB Output is correct
8 Correct 117 ms 129496 KB Output is correct
9 Correct 115 ms 129472 KB Output is correct
10 Correct 111 ms 128460 KB Output is correct
11 Correct 111 ms 128588 KB Output is correct
12 Correct 100 ms 126440 KB Output is correct
13 Correct 112 ms 129644 KB Output is correct
14 Correct 110 ms 129592 KB Output is correct
15 Correct 112 ms 129612 KB Output is correct
16 Correct 105 ms 128736 KB Output is correct
17 Correct 106 ms 128528 KB Output is correct
18 Correct 96 ms 126140 KB Output is correct
19 Correct 2029 ms 228440 KB Output is correct
20 Correct 2060 ms 228516 KB Output is correct
21 Correct 2036 ms 228428 KB Output is correct
22 Correct 1232 ms 226012 KB Output is correct
23 Correct 1063 ms 226192 KB Output is correct
24 Correct 350 ms 152984 KB Output is correct
25 Correct 1675 ms 227980 KB Output is correct
26 Correct 1659 ms 227932 KB Output is correct
27 Correct 1455 ms 226284 KB Output is correct
28 Correct 1338 ms 228276 KB Output is correct
29 Correct 974 ms 225756 KB Output is correct
30 Correct 290 ms 145388 KB Output is correct
31 Correct 2537 ms 228320 KB Output is correct
32 Correct 2396 ms 231220 KB Output is correct
33 Correct 2037 ms 231104 KB Output is correct
34 Correct 1331 ms 228172 KB Output is correct
35 Correct 1104 ms 228252 KB Output is correct
36 Correct 374 ms 153912 KB Output is correct
37 Correct 2475 ms 231348 KB Output is correct
38 Correct 2513 ms 231404 KB Output is correct
39 Correct 2261 ms 230236 KB Output is correct
40 Correct 1367 ms 229924 KB Output is correct
41 Correct 975 ms 227508 KB Output is correct
42 Correct 279 ms 146380 KB Output is correct
43 Execution timed out 3061 ms 284772 KB Time limit exceeded
44 Halted 0 ms 0 KB -