oj.uz

Submission #365594

# Submission time Handle Problem Language Result Execution time Memory
365594 2021-02-11T22:35:31 Z mat_v Examination (JOI19_examination) C++14
20 / 100
 251 ms 15524 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 > b.xx;
}

int ans[N];
int br;
int bit[10 * N][2];
void dodaj(int x, int idx){
    while(x > 0){
        bit[x][idx]++;
        x -= (x&-x);
    }
}
int query(int x, int idx){
    int sol = 0;
    while(x <= 100001){
        sol += bit[x][idx];
        x += (x&-x);
    }
    return sol;
}

struct fw{
    int idx;
    int poz;
    int znk;
    int val;
    int zakoju;
};

bool cmp2(fw a, fw b){
    return a.poz < b.poz;
}

int dokle(int x){
    if(x > niz[1].xx)return 0;
    if(x <= niz[n].xx)return n;
    int l = 1;
    int r = n;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if(niz[mid].xx >= x)l = mid;
        else r = mid - 1;
    }
    return l;
}


vector<fw> v;

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);
        svi.pb(niz[i].xx + niz[i].yy);
    }
    sort(niz + 1, niz + n + 1, cmp);
    ff(i,1,q){
        int a,b,c;
        cin >> a >> b >> c;
        int prvi = dokle(a);
        int drugi = dokle(c - b);
        assert(prvi == n || niz[prvi + 1].xx < a);
        assert(prvi == 0 || niz[prvi].xx >= a);
        if(c - b <= a){
            v.pb({0,prvi,1,b,i});
        }
        else{
            assert(false);
            v.pb({0,drugi,1,b,i});
            if(drugi < prvi){
                v.pb({1,drugi,-1,c,i});
                v.pb({1,prvi,1,c,i});
            }
        }
        kv[i].x = a;
        kv[i].y = b;
        kv[i].z = c;
        svi.pb(a);
        svi.pb(b);
        svi.pb(c);
    }
    sort(svi.begin(), svi.end());
    int last = -1;
    for(auto c:svi){
        if(c == last)continue;
        br++;
        slika[c] = br;
        last = c;
    }

    sort(v.begin(), v.end(), cmp2);

    int tr = 0;
    ff(i,1,n){
        dodaj(niz[i].yy + 1, 0);
        dodaj(slika[niz[i].xx + niz[i].yy], 1);
        while(1){
            int sta = v.size();
            if(tr == sta)break;
            while(v[tr].poz < i)tr++;
            if(v[tr].poz > i)break;
            ans[v[tr].zakoju] += (v[tr].znk)*query(v[tr].val + 1,v[tr].idx);
            tr++;
        }
    }
    ff(i,1,q)cout << ans[i] << "\n";


    return 0;
}
/*
5 1
35 100
70 70
45 15
80 40
20 95
20 50 120



*/

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:91:5: note: in expansion of macro 'ff'
   91 |     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:98:5: note: in expansion of macro 'ff'
   98 |     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:135:5: note: in expansion of macro 'ff'
  135 |     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:147:5: note: in expansion of macro 'ff'
  147 |     ff(i,1,q)cout << ans[i] << "\n";
      |     ^~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 15524 KB Output is correct
2 Correct 235 ms 15448 KB Output is correct
3 Correct 251 ms 15448 KB Output is correct
4 Correct 172 ms 13144 KB Output is correct
5 Correct 208 ms 13304 KB Output is correct
6 Correct 96 ms 9304 KB Output is correct
7 Correct 221 ms 15300 KB Output is correct
8 Correct 230 ms 15352 KB Output is correct
9 Correct 212 ms 15192 KB Output is correct
10 Correct 162 ms 12632 KB Output is correct
11 Correct 168 ms 14296 KB Output is correct
12 Correct 77 ms 10208 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 15524 KB Output is correct
2 Correct 235 ms 15448 KB Output is correct
3 Correct 251 ms 15448 KB Output is correct
4 Correct 172 ms 13144 KB Output is correct
5 Correct 208 ms 13304 KB Output is correct
6 Correct 96 ms 9304 KB Output is correct
7 Correct 221 ms 15300 KB Output is correct
8 Correct 230 ms 15352 KB Output is correct
9 Correct 212 ms 15192 KB Output is correct
10 Correct 162 ms 12632 KB Output is correct
11 Correct 168 ms 14296 KB Output is correct
12 Correct 77 ms 10208 KB Output is correct
13 Runtime error 39 ms 6116 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -