oj.uz

Submission #877197

# Submission time Handle Problem Language Result Execution time Memory
877197 2023-11-23T03:19:38 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 316 ms 57872 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 7e5 + 10, MOD = 1e9 + 7;

int n,q,s[N],t[N],x[N],y[N],z[N],sm[N],res[N],X[N],Y[N],Z[N];
vector<int> a,p,qq;
struct segtree{
    int t[N * 4];
    void build(int v = 1,int tl = 1,int tr = N){
        t[v] =0 ;
        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
    }
    void upd(int pos,int val,int v = 1,int tl = 1,int tr = N){
        if(tl == tr){
            t[v] += val;
        }else{
            int tm = (tl + tr) >> 1;
            if(pos <= tm) upd(pos,val,v+v,tl,tm);
            else upd(pos,val,v+v+1,tm+1,tr);
            t[v] = t[v + v] + t[v + v + 1];
        }
    }
    int get(int l,int r,int v = 1,int tl = 1,int tr = N){
        if(l > r || tl > r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
}A,B;
int find(int val){
    int it = lower_bound(a.begin(),a.end(),val) - a.begin();
    return it + 1;
}
bool cmp(int i,int j){
    return (sm[i] > sm[j]);
}
bool cmp1(int i,int j){
    return (z[i] > z[j]);
}
bool cmp2(int i,int j){
    return (y[i] > y[j]);
}
bool cmp3(int i,int j){
    return (t[i] > t[j]);
}
void test(){
    A.build();
    B.build();
    cin >> n >> q;
    p.resize(n);
    iota(p.begin(),p.end(),1);
    qq.resize(q);
    iota(qq.begin(),qq.end(),1);
    for(int i = 1;i <= n;i++){
        cin >> s[i] >> t[i];
        sm[i] = s[i] + t[i];
        a.push_back(s[i]);
        a.push_back(t[i]);
        a.push_back(sm[i]);
    }
    for(int i = 1;i <= q;i++){
        cin >> x[i] >> y[i] >> z[i];
        X[i] = x[i];
        Y[i] = y[i];
        Z[i] = z[i];
        a.push_back(x[i]);
        a.push_back(y[i]);
        a.push_back(z[i]);
    }
    sort(a.begin(),a.end());
    for(int i = 1;i <= n;i++){
        s[i] = find(s[i]);t[i] = find(t[i]);sm[i] = find(sm[i]);
    }
    for(int i = 1;i <= q;i++){
        x[i] = find(x[i]);y[i] = find(y[i]);z[i] = find(z[i]);
    }
    sort(p.begin(),p.end(),cmp);
    sort(qq.begin(),qq.end(),cmp1);
    int it = 0;
    vector<pair<int,int>> f;
    vector<int> pos;
    for(int i:qq){
        if(X[i] + Y[i] >= Z[i]){
            pos.push_back(i);
            continue;
        }
        while(it < p.size() && sm[p[it]] >= z[i]){
            A.upd(s[p[it]],1);
            B.upd(t[p[it]],1);
            f.push_back({s[p[it]],t[p[it]]});
            it++;
        }
        int col = 0;
        res[i] = A.get(x[i],N) + B.get(y[i],N) - it;
    }
    A.build();
    it = 0;
    sort(p.begin(),p.end(),cmp3);
    sort(pos.begin(),pos.end(),cmp2);
    vector<int> all;
    for(auto i:pos){

        while(it < n && t[p[it]] >= y[i]){
            A.upd(s[p[it]],1);
            all.push_back(s[p[it]]);
            it++;
        }
        int col = 0;
        // for(auto j:all){
        //     if(j >= x[i]) col++;
        // }
        // res[i] = col;
        // cout << i << ' ' << res[i] << "x\n";
        res[i] = A.get(x[i],N);
    }
    for(int i = 1;i <= q;i++){
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Compilation message

examination.cpp: In function 'void test()':
examination.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while(it < p.size() && sm[p[it]] >= z[i]){
      |               ~~~^~~~~~~~~~
examination.cpp:97:13: warning: unused variable 'col' [-Wunused-variable]
   97 |         int col = 0;
      |             ^~~
examination.cpp:112:13: warning: unused variable 'col' [-Wunused-variable]
  112 |         int col = 0;
      |             ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39620 KB Output is correct
2 Correct 8 ms 39512 KB Output is correct
3 Correct 8 ms 39424 KB Output is correct
4 Correct 8 ms 39516 KB Output is correct
5 Correct 8 ms 39528 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Correct 14 ms 39772 KB Output is correct
8 Correct 15 ms 39772 KB Output is correct
9 Correct 14 ms 39772 KB Output is correct
10 Correct 13 ms 39768 KB Output is correct
11 Correct 13 ms 39768 KB Output is correct
12 Correct 12 ms 39772 KB Output is correct
13 Correct 13 ms 39836 KB Output is correct
14 Correct 13 ms 39772 KB Output is correct
15 Correct 13 ms 39904 KB Output is correct
16 Correct 14 ms 39892 KB Output is correct
17 Correct 13 ms 39772 KB Output is correct
18 Correct 10 ms 39768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 53704 KB Output is correct
2 Correct 209 ms 54728 KB Output is correct
3 Correct 223 ms 53540 KB Output is correct
4 Correct 160 ms 52328 KB Output is correct
5 Correct 156 ms 53356 KB Output is correct
6 Correct 111 ms 52632 KB Output is correct
7 Correct 211 ms 53980 KB Output is correct
8 Correct 210 ms 54480 KB Output is correct
9 Correct 193 ms 52932 KB Output is correct
10 Correct 140 ms 52160 KB Output is correct
11 Correct 142 ms 52676 KB Output is correct
12 Correct 76 ms 51268 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 53704 KB Output is correct
2 Correct 209 ms 54728 KB Output is correct
3 Correct 223 ms 53540 KB Output is correct
4 Correct 160 ms 52328 KB Output is correct
5 Correct 156 ms 53356 KB Output is correct
6 Correct 111 ms 52632 KB Output is correct
7 Correct 211 ms 53980 KB Output is correct
8 Correct 210 ms 54480 KB Output is correct
9 Correct 193 ms 52932 KB Output is correct
10 Correct 140 ms 52160 KB Output is correct
11 Correct 142 ms 52676 KB Output is correct
12 Correct 76 ms 51268 KB Output is correct
13 Correct 290 ms 55232 KB Output is correct
14 Correct 309 ms 56044 KB Output is correct
15 Correct 212 ms 54724 KB Output is correct
16 Correct 213 ms 54248 KB Output is correct
17 Correct 209 ms 54352 KB Output is correct
18 Correct 120 ms 53516 KB Output is correct
19 Correct 305 ms 54856 KB Output is correct
20 Correct 295 ms 55612 KB Output is correct
21 Correct 275 ms 54388 KB Output is correct
22 Correct 147 ms 52284 KB Output is correct
23 Correct 141 ms 52984 KB Output is correct
24 Correct 75 ms 51588 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39620 KB Output is correct
2 Correct 8 ms 39512 KB Output is correct
3 Correct 8 ms 39424 KB Output is correct
4 Correct 8 ms 39516 KB Output is correct
5 Correct 8 ms 39528 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Correct 14 ms 39772 KB Output is correct
8 Correct 15 ms 39772 KB Output is correct
9 Correct 14 ms 39772 KB Output is correct
10 Correct 13 ms 39768 KB Output is correct
11 Correct 13 ms 39768 KB Output is correct
12 Correct 12 ms 39772 KB Output is correct
13 Correct 13 ms 39836 KB Output is correct
14 Correct 13 ms 39772 KB Output is correct
15 Correct 13 ms 39904 KB Output is correct
16 Correct 14 ms 39892 KB Output is correct
17 Correct 13 ms 39772 KB Output is correct
18 Correct 10 ms 39768 KB Output is correct
19 Correct 216 ms 53704 KB Output is correct
20 Correct 209 ms 54728 KB Output is correct
21 Correct 223 ms 53540 KB Output is correct
22 Correct 160 ms 52328 KB Output is correct
23 Correct 156 ms 53356 KB Output is correct
24 Correct 111 ms 52632 KB Output is correct
25 Correct 211 ms 53980 KB Output is correct
26 Correct 210 ms 54480 KB Output is correct
27 Correct 193 ms 52932 KB Output is correct
28 Correct 140 ms 52160 KB Output is correct
29 Correct 142 ms 52676 KB Output is correct
30 Correct 76 ms 51268 KB Output is correct
31 Correct 290 ms 55232 KB Output is correct
32 Correct 309 ms 56044 KB Output is correct
33 Correct 212 ms 54724 KB Output is correct
34 Correct 213 ms 54248 KB Output is correct
35 Correct 209 ms 54352 KB Output is correct
36 Correct 120 ms 53516 KB Output is correct
37 Correct 305 ms 54856 KB Output is correct
38 Correct 295 ms 55612 KB Output is correct
39 Correct 275 ms 54388 KB Output is correct
40 Correct 147 ms 52284 KB Output is correct
41 Correct 141 ms 52984 KB Output is correct
42 Correct 75 ms 51588 KB Output is correct
43 Correct 316 ms 57508 KB Output is correct
44 Correct 305 ms 56584 KB Output is correct
45 Correct 284 ms 56764 KB Output is correct
46 Correct 231 ms 56332 KB Output is correct
47 Correct 217 ms 56116 KB Output is correct
48 Correct 122 ms 52428 KB Output is correct
49 Correct 296 ms 56380 KB Output is correct
50 Correct 303 ms 57232 KB Output is correct
51 Correct 277 ms 57872 KB Output is correct
52 Correct 197 ms 55748 KB Output is correct
53 Correct 148 ms 54464 KB Output is correct