oj.uz

Submission #959344

# Submission time Handle Problem Language Result Execution time Memory
959344 2024-04-08T05:03:39 Z irmuun Examination (JOI19_examination) C++17
41 / 100
 225 ms 40868 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,0,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0ll;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]+=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
    void set(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        set(node*2,l,mid,k,val);
        set(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,q;
    cin>>n>>q;
    ll s[n],t[n];
    const ll N=2e5;
    vector<ll>upd[N+5],upd2[N+5];
    for(ll i=0;i<n;i++){
        cin>>s[i]>>t[i];
        upd[s[i]].pb(t[i]);
        upd2[s[i]+t[i]].pb(i);
    }
    ll x[q],y[q],z[q];
    vector<ll>ans(q,0);
    vector<pair<ll,ll>>ask[N+5];
    vector<ll>que[N+5];
    for(ll i=0;i<q;i++){
        cin>>x[i]>>y[i]>>z[i];
        if(z[i]<=x[i]+y[i]){
            ask[x[i]].pb({y[i],i});
        }
        else{
            que[z[i]].pb(i);
        }
    }
    segtree sg(N);
    for(ll i=N;i>=0;i--){
        for(auto y:upd[i]){
            sg.update(1,0,N,y,1);
        }
        for(auto [y,j]:ask[i]){
            ans[j]=sg.query(1,0,N,y,N);
        }
    }
    for(ll i=0;i<=N;i++){
        sg.set(1,0,N,i,0);
    }
    for(ll i=N;i>=0;i--){
        for(auto j:upd2[i]){
            sg.update(1,0,N,s[j],1);
        }
        for(auto j:que[i]){
            ans[j]=sg.query(1,0,N,x[j],N);
        }
    }
    for(ll i=0;i<=N;i++){
        sg.set(1,0,N,i,0);
    }
    for(ll i=N;i>=0;i--){
        for(auto j:upd2[i]){
            sg.update(1,0,N,t[j],1);
        }
        for(auto j:que[i]){
            ans[j]-=sg.query(1,0,N,0,y[j]-1);
        }
    }
    for(ll i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 25528 KB Output is correct
2 Correct 49 ms 25424 KB Output is correct
3 Correct 48 ms 25432 KB Output is correct
4 Runtime error 33 ms 38488 KB Execution killed with signal 7
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 37892 KB Output is correct
2 Correct 187 ms 37864 KB Output is correct
3 Correct 222 ms 37732 KB Output is correct
4 Correct 151 ms 37604 KB Output is correct
5 Correct 150 ms 36024 KB Output is correct
6 Correct 117 ms 34836 KB Output is correct
7 Correct 188 ms 37808 KB Output is correct
8 Correct 211 ms 37712 KB Output is correct
9 Correct 180 ms 38028 KB Output is correct
10 Correct 133 ms 35060 KB Output is correct
11 Correct 142 ms 37356 KB Output is correct
12 Correct 100 ms 34032 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 37892 KB Output is correct
2 Correct 187 ms 37864 KB Output is correct
3 Correct 222 ms 37732 KB Output is correct
4 Correct 151 ms 37604 KB Output is correct
5 Correct 150 ms 36024 KB Output is correct
6 Correct 117 ms 34836 KB Output is correct
7 Correct 188 ms 37808 KB Output is correct
8 Correct 211 ms 37712 KB Output is correct
9 Correct 180 ms 38028 KB Output is correct
10 Correct 133 ms 35060 KB Output is correct
11 Correct 142 ms 37356 KB Output is correct
12 Correct 100 ms 34032 KB Output is correct
13 Correct 225 ms 37924 KB Output is correct
14 Correct 198 ms 40800 KB Output is correct
15 Correct 196 ms 40368 KB Output is correct
16 Correct 181 ms 39764 KB Output is correct
17 Correct 156 ms 38324 KB Output is correct
18 Correct 110 ms 35644 KB Output is correct
19 Correct 224 ms 40868 KB Output is correct
20 Correct 206 ms 40784 KB Output is correct
21 Correct 212 ms 40724 KB Output is correct
22 Correct 150 ms 37044 KB Output is correct
23 Correct 141 ms 38996 KB Output is correct
24 Correct 99 ms 35148 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 25528 KB Output is correct
2 Correct 49 ms 25424 KB Output is correct
3 Correct 48 ms 25432 KB Output is correct
4 Runtime error 33 ms 38488 KB Execution killed with signal 7
5 Halted 0 ms 0 KB -