oj.uz

답안 #673487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673487 2022-12-20T17:13:37 Z Carmel_Ab1 Examination (JOI19_examination) C++17
20 / 100
 237 ms 24816 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map


template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}
struct seg{
    seg* lp=0,*rp=0;
    int l,r,m;
    int sum=0;

    seg(int l,int r):l(l),r(r),m((l+r)/2){}

    void expand(){
        if(!lp)lp=new seg(l,m);
        if(!rp)rp=new seg(m,r);
    }
    void upd(int i,int v){
        sum+=v;
        if(l+1==r)
            return;
        expand();
        if(i<m)
            lp->upd(i,v);
        else
            rp->upd(i,v);
    }

    int qur(int a,int b){
        if(b<=l || r<=a)
            return 0;
        if(a<=l && r<=b)
            return sum;
        expand();
        return lp->qur(a,b) + rp->qur(a,b);
    }
};

void solve() {
    int n,q;
    cin >> n >> q;
    vvl a(n,vl(2));
    for(int i=0 ;i<n; i++)
        cin >> a[i][0] >> a[i][1];

    vvl queries(q,vl(4));
    for(int i=0; i<q; i++){
        cin >>queries[i][0] >> queries[i][1] >> queries[i][2];
        queries[i][3]=i;
    }
    sort(all(a));
    sort(all(queries));

    vi ans(q);
    seg ST(0,1e9 +10);

    for(int i=0; i<n; i++)
        ST.upd(a[i][1],1);

    for(int i=0,j=0; i<q; i++){
        while(j<n && a[j][0]<queries[i][0])
            ST.upd(a[j++][1],-1);
        ans[queries[i][3]] = ST.qur(queries[i][1],1e9 + 2);
    }

    for(int x:ans)
        cout << x << "\n";
}

Subtask #1
0 / 2.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 24816 KB Output is correct
2 Correct 231 ms 24780 KB Output is correct
3 Correct 237 ms 24816 KB Output is correct
4 Correct 138 ms 15492 KB Output is correct
5 Correct 178 ms 24732 KB Output is correct
6 Correct 142 ms 14876 KB Output is correct
7 Correct 188 ms 24804 KB Output is correct
8 Correct 225 ms 24524 KB Output is correct
9 Correct 177 ms 24452 KB Output is correct
10 Correct 157 ms 24540 KB Output is correct
11 Correct 140 ms 15380 KB Output is correct
12 Correct 115 ms 14328 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 24816 KB Output is correct
2 Correct 231 ms 24780 KB Output is correct
3 Correct 237 ms 24816 KB Output is correct
4 Correct 138 ms 15492 KB Output is correct
5 Correct 178 ms 24732 KB Output is correct
6 Correct 142 ms 14876 KB Output is correct
7 Correct 188 ms 24804 KB Output is correct
8 Correct 225 ms 24524 KB Output is correct
9 Correct 177 ms 24452 KB Output is correct
10 Correct 157 ms 24540 KB Output is correct
11 Correct 140 ms 15380 KB Output is correct
12 Correct 115 ms 14328 KB Output is correct
13 Incorrect 224 ms 24816 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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