oj.uz

Submission #364922

# Submission time Handle Problem Language Result Execution time Memory
364922 2021-02-10T12:55:41 Z mat_v Examination (JOI19_examination) C++14
2 / 100
 3000 ms 292272 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 84 ms 12908 KB Output is correct
8 Correct 86 ms 12780 KB Output is correct
9 Correct 90 ms 13184 KB Output is correct
10 Correct 46 ms 4588 KB Output is correct
11 Correct 51 ms 4716 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 89 ms 12780 KB Output is correct
14 Correct 88 ms 12708 KB Output is correct
15 Correct 89 ms 12896 KB Output is correct
16 Correct 47 ms 4204 KB Output is correct
17 Correct 37 ms 4332 KB Output is correct
18 Correct 3 ms 620 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 292272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 292272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 84 ms 12908 KB Output is correct
8 Correct 86 ms 12780 KB Output is correct
9 Correct 90 ms 13184 KB Output is correct
10 Correct 46 ms 4588 KB Output is correct
11 Correct 51 ms 4716 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 89 ms 12780 KB Output is correct
14 Correct 88 ms 12708 KB Output is correct
15 Correct 89 ms 12896 KB Output is correct
16 Correct 47 ms 4204 KB Output is correct
17 Correct 37 ms 4332 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Execution timed out 3088 ms 292272 KB Time limit exceeded
20 Halted 0 ms 0 KB -