oj.uz

Submission #877187

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

int n,q,s[N],t[N],x[N],y[N],z[N],sm[N],res[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]);
}
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];
        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;
    for(int i:qq){
        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;
        for(auto [a,b]:f){
            if(a >= x[i] && b >= y[i]){
                col++;
            }
        }
        res[i] = col;
    }
    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:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while(it < p.size() && sm[p[it]] >= z[i]){
      |               ~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33244 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 6 ms 33372 KB Output is correct
7 Correct 20 ms 33836 KB Output is correct
8 Correct 20 ms 33844 KB Output is correct
9 Correct 20 ms 33840 KB Output is correct
10 Correct 14 ms 33628 KB Output is correct
11 Correct 19 ms 33708 KB Output is correct
12 Correct 16 ms 33548 KB Output is correct
13 Correct 27 ms 33800 KB Output is correct
14 Correct 28 ms 33628 KB Output is correct
15 Correct 28 ms 33624 KB Output is correct
16 Correct 21 ms 33628 KB Output is correct
17 Correct 14 ms 33628 KB Output is correct
18 Correct 9 ms 33496 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 44340 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 3063 ms 44340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33244 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 6 ms 33372 KB Output is correct
7 Correct 20 ms 33836 KB Output is correct
8 Correct 20 ms 33844 KB Output is correct
9 Correct 20 ms 33840 KB Output is correct
10 Correct 14 ms 33628 KB Output is correct
11 Correct 19 ms 33708 KB Output is correct
12 Correct 16 ms 33548 KB Output is correct
13 Correct 27 ms 33800 KB Output is correct
14 Correct 28 ms 33628 KB Output is correct
15 Correct 28 ms 33624 KB Output is correct
16 Correct 21 ms 33628 KB Output is correct
17 Correct 14 ms 33628 KB Output is correct
18 Correct 9 ms 33496 KB Output is correct
19 Execution timed out 3063 ms 44340 KB Time limit exceeded
20 Halted 0 ms 0 KB -