oj.uz

Submission #673510

# Submission time Handle Problem Language Result Execution time Memory
673510 2022-12-20T19:32:17 Z Carmel_Ab1 Examination (JOI19_examination) C++17
22 / 100
 3000 ms 24024 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);
    }
};

/*
 Basically what we do is split the queries into 2 types:
 1. queries where A+B>=C, then we only need to count S>=A, T>=B, (and then it applies that S+T>=A+B>=C).
 So we only need to count how many fulfil S>=A, T>=B.
 This can be done offline - sorting queries and pairs by S/A, then querying a segment tree on [B,inf].


 */
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);
        if(queries[i][0]+queries[i][1]>=queries[i][2])
            ans[queries[i][3]] = ST.qur(queries[i][1],1e9 + 2);
    }

    for(int i=0; i<q; i++){
        ll A=queries[i][0],B=queries[i][1],C=queries[i][2],ix=queries[i][3];
        if(A+B>=C)
            continue;

        for(int j=0; j<n; j++){
            ll S=a[j][0],T=a[j][1];
            if(S+T>=C && T>=B)
                ans[ix]++;
        }
    }
    for(int i=0; i<q; i++){
        ll A=queries[i][0],B=queries[i][1],C=queries[i][2],ix=queries[i][3];
        if(A+B>=C)
            continue;

        for(int j=0; j<n; j++){
            ll S=a[j][0],T=a[j][1];
            if(S+T>=C && S<A)
                ans[ix]--;
        }
    }

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 36 ms 8216 KB Output is correct
8 Correct 31 ms 8252 KB Output is correct
9 Correct 32 ms 8148 KB Output is correct
10 Correct 17 ms 804 KB Output is correct
11 Correct 23 ms 8200 KB Output is correct
12 Correct 14 ms 720 KB Output is correct
13 Correct 14 ms 10312 KB Output is correct
14 Correct 13 ms 10352 KB Output is correct
15 Correct 14 ms 10336 KB Output is correct
16 Correct 12 ms 10344 KB Output is correct
17 Correct 13 ms 724 KB Output is correct
18 Correct 7 ms 712 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 23968 KB Output is correct
2 Correct 223 ms 23992 KB Output is correct
3 Correct 237 ms 24024 KB Output is correct
4 Correct 138 ms 14324 KB Output is correct
5 Correct 176 ms 23364 KB Output is correct
6 Correct 132 ms 14244 KB Output is correct
7 Correct 201 ms 23904 KB Output is correct
8 Correct 212 ms 23500 KB Output is correct
9 Correct 179 ms 23468 KB Output is correct
10 Correct 150 ms 23232 KB Output is correct
11 Correct 137 ms 14100 KB Output is correct
12 Correct 114 ms 13876 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 23968 KB Output is correct
2 Correct 223 ms 23992 KB Output is correct
3 Correct 237 ms 24024 KB Output is correct
4 Correct 138 ms 14324 KB Output is correct
5 Correct 176 ms 23364 KB Output is correct
6 Correct 132 ms 14244 KB Output is correct
7 Correct 201 ms 23904 KB Output is correct
8 Correct 212 ms 23500 KB Output is correct
9 Correct 179 ms 23468 KB Output is correct
10 Correct 150 ms 23232 KB Output is correct
11 Correct 137 ms 14100 KB Output is correct
12 Correct 114 ms 13876 KB Output is correct
13 Execution timed out 3025 ms 23164 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 36 ms 8216 KB Output is correct
8 Correct 31 ms 8252 KB Output is correct
9 Correct 32 ms 8148 KB Output is correct
10 Correct 17 ms 804 KB Output is correct
11 Correct 23 ms 8200 KB Output is correct
12 Correct 14 ms 720 KB Output is correct
13 Correct 14 ms 10312 KB Output is correct
14 Correct 13 ms 10352 KB Output is correct
15 Correct 14 ms 10336 KB Output is correct
16 Correct 12 ms 10344 KB Output is correct
17 Correct 13 ms 724 KB Output is correct
18 Correct 7 ms 712 KB Output is correct
19 Correct 224 ms 23968 KB Output is correct
20 Correct 223 ms 23992 KB Output is correct
21 Correct 237 ms 24024 KB Output is correct
22 Correct 138 ms 14324 KB Output is correct
23 Correct 176 ms 23364 KB Output is correct
24 Correct 132 ms 14244 KB Output is correct
25 Correct 201 ms 23904 KB Output is correct
26 Correct 212 ms 23500 KB Output is correct
27 Correct 179 ms 23468 KB Output is correct
28 Correct 150 ms 23232 KB Output is correct
29 Correct 137 ms 14100 KB Output is correct
30 Correct 114 ms 13876 KB Output is correct
31 Execution timed out 3025 ms 23164 KB Time limit exceeded
32 Halted 0 ms 0 KB -