oj.uz

Submission #959341

# Submission time Handle Problem Language Result Execution time Memory
959341 2024-04-08T04:38:22 Z irmuun Examination (JOI19_examination) C++17
20 / 100
 126 ms 29060 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];
    }
};

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];
    for(ll i=0;i<n;i++){
        cin>>s[i]>>t[i];
        upd[s[i]].pb(t[i]);
    }
    ll x[q],y[q],z[q];
    vector<ll>ans(q,0);
    vector<pair<ll,ll>>ask[N+5];
    for(ll i=0;i<q;i++){
        cin>>x[i]>>y[i]>>z[i];
        ask[x[i]].pb({y[i],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<q;i++){
        cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 15964 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 89 ms 26064 KB Output is correct
2 Correct 126 ms 26040 KB Output is correct
3 Correct 88 ms 25968 KB Output is correct
4 Correct 71 ms 26056 KB Output is correct
5 Correct 70 ms 26260 KB Output is correct
6 Correct 50 ms 25484 KB Output is correct
7 Correct 82 ms 28500 KB Output is correct
8 Correct 84 ms 28488 KB Output is correct
9 Correct 85 ms 28292 KB Output is correct
10 Correct 66 ms 25284 KB Output is correct
11 Correct 70 ms 27472 KB Output is correct
12 Correct 54 ms 25076 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 26064 KB Output is correct
2 Correct 126 ms 26040 KB Output is correct
3 Correct 88 ms 25968 KB Output is correct
4 Correct 71 ms 26056 KB Output is correct
5 Correct 70 ms 26260 KB Output is correct
6 Correct 50 ms 25484 KB Output is correct
7 Correct 82 ms 28500 KB Output is correct
8 Correct 84 ms 28488 KB Output is correct
9 Correct 85 ms 28292 KB Output is correct
10 Correct 66 ms 25284 KB Output is correct
11 Correct 70 ms 27472 KB Output is correct
12 Correct 54 ms 25076 KB Output is correct
13 Incorrect 96 ms 29060 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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