Submission #364922

#	Time	Username	Problem	Language	Result	Execution time	Memory
364922		mat_v	Examination (JOI19_examination)	C++14	2 / 100	3088 ms	292272 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define N 100005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,q;
pii niz[N];
struct upit{
    int x,y,z;
    int idx;
}kv[N];
map<int, int>slika;

bool cmp(pii a, pii b){
    return (a.xx + a.yy) > (b.xx + b.yy);
}

bool cmp2(upit a, upit b){
    return a.z > b.z;
}
int ans[N];

int br;

map<pair<int,int>, int> bit;

void dodaj(int x, int y){
    for(int i = x;i > 0; i -= (i&-i)){
        for(int j = y;j > 0; j -= (j&-j)){
            bit[{i,j}]++;
        }

    }
}
int kveri(int x, int y){
    int sol = 0;
    for(int i = x;i <= br; i += (i&-i)){
        for(int j = y;j <= br; j += (j&-j)){
            sol += bit[{i,j}];
        }
    }
    return sol;
}


int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    vector<int> svi;

    cin >> n >> q;
    ff(i,1,n){
        cin >> niz[i].xx >> niz[i].yy;
        svi.pb(niz[i].xx);
        svi.pb(niz[i].yy);
    }
    sort(niz + 1, niz + n + 1, cmp);

    ff(i,1,q){
        cin >> kv[i].x >> kv[i].y >> kv[i].z;
        svi.pb(kv[i].x);
        svi.pb(kv[i].y);
        kv[i].idx = i;
    }
    sort(svi.begin(), svi.end());
    int last = -1;

    for(auto c:svi){
        if(c == last)continue;
        br++;
        slika[c] = br;
        last = c;
    }
    sort(kv + 1, kv + q + 1, cmp2);

    int tr = 0;
    ff(i,1,q){

        while(tr < n && niz[tr + 1].xx + niz[tr + 1].yy >= kv[i].z){
            ++tr;
            dodaj(slika[niz[tr].xx], slika[niz[tr].yy]);
        }
        ans[kv[i].idx] = kveri(slika[kv[i].x], slika[kv[i].y]);

    }

    ff(i,1,q){
        cout << ans[i] << "\n";
    }


    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
examination.cpp:70:5: note: in expansion of macro 'ff'
   70 |     ff(i,1,n){
      |     ^~
examination.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
examination.cpp:77:5: note: in expansion of macro 'ff'
   77 |     ff(i,1,q){
      |     ^~
examination.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
examination.cpp:95:5: note: in expansion of macro 'ff'
   95 |     ff(i,1,q){
      |     ^~
examination.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
examination.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,1,q){
      |     ^~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57