oj.uz

답안 #959340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959340 2024-04-08T04:37:02 Z irmuun Examination (JOI19_examination) C++17
0 / 100
 103 ms 28500 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,1,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,1,N,y,1);
        }
        for(auto [y,j]:ask[i]){
            ans[j]=sg.query(1,1,N,y,N);
        }
    }
    for(ll i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 15960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 28100 KB Output is correct
2 Correct 103 ms 28500 KB Output is correct
3 Correct 88 ms 28500 KB Output is correct
4 Incorrect 89 ms 27964 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 28100 KB Output is correct
2 Correct 103 ms 28500 KB Output is correct
3 Correct 88 ms 28500 KB Output is correct
4 Incorrect 89 ms 27964 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 15960 KB Output isn't correct
2 Halted 0 ms 0 KB -