oj.uz

Submission #676417

# Submission time Handle Problem Language Result Execution time Memory
676417 2022-12-30T21:08:50 Z urosk Examination (JOI19_examination) C++14
20 / 100
 2864 ms 231320 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(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
0 / 2.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2089 ms 228628 KB Output is correct
2 Correct 2057 ms 230868 KB Output is correct
3 Correct 2148 ms 231056 KB Output is correct
4 Correct 1210 ms 227740 KB Output is correct
5 Correct 1055 ms 228052 KB Output is correct
6 Correct 347 ms 153960 KB Output is correct
7 Correct 1849 ms 230564 KB Output is correct
8 Correct 1688 ms 230348 KB Output is correct
9 Correct 1431 ms 228508 KB Output is correct
10 Correct 1352 ms 229900 KB Output is correct
11 Correct 981 ms 227416 KB Output is correct
12 Correct 276 ms 146292 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2089 ms 228628 KB Output is correct
2 Correct 2057 ms 230868 KB Output is correct
3 Correct 2148 ms 231056 KB Output is correct
4 Correct 1210 ms 227740 KB Output is correct
5 Correct 1055 ms 228052 KB Output is correct
6 Correct 347 ms 153960 KB Output is correct
7 Correct 1849 ms 230564 KB Output is correct
8 Correct 1688 ms 230348 KB Output is correct
9 Correct 1431 ms 228508 KB Output is correct
10 Correct 1352 ms 229900 KB Output is correct
11 Correct 981 ms 227416 KB Output is correct
12 Correct 276 ms 146292 KB Output is correct
13 Incorrect 2864 ms 231320 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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