oj.uz

Submission #873533

# Submission time Handle Problem Language Result Execution time Memory
873533 2023-11-15T09:08:05 Z NintsiChkhaidze Examination (JOI19_examination) C++17
2 / 100
 3000 ms 37280 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l + r)>>1) + 1,r
#define pii pair<int,int>
#define int ll
using namespace std;

const int N = 1e5 + 5;

int S[N],T[N],X[N],Y[N],Z[N],ans[N];
map <int,int> mp;
vector <int> v[4*N];

vector <int> merge(vector <int> x, vector <int> y){
    if (!x.size()) return y;
    if (!y.size()) return x;

    int l1=0,l2=0;
    vector <int> vnew;
    for (int i = 0; i < (int)x.size() + (int)y.size(); i++){
        if (l1 == x.size()){
            vnew.pb(y[l2++]);
            continue;
        }
        if (l2 == y.size()){
            vnew.pb(x[l1++]);
            continue;
        }

        if (x[l1] < y[l2]) {
            vnew.pb(x[l1++]);
        }else{
            vnew.pb(y[l2++]);
        }
    }
    return vnew;
}
void upd(int h,int l,int r,int idx,int val){
    if (l == r){
        int len = v[h].size(),l = 0;
        vector <int> vnew;
        for (int i=0;i<=len;i++){
            if (val == -1){
                vnew.pb(v[h][l++]);
                continue;
            }
            if (l < len && v[h][l] < val) {
                vnew.pb(v[h][l++]);
            }else{
                vnew.pb(val);
                val = -1;
            }
        }

        v[h] = vnew;
        return;
    }

    if (idx > (l + r)/2) upd(right,idx,val);
    else upd(left,idx,val);
    v[h] = merge(v[h*2],v[h*2 + 1]);
}

int get(int h,int l,int r,int L,int R,int k){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R){
        int le = 0,ri = v[h].size() - 1,res=-1;
        while (le <= ri){
            int mid = (le + ri)/2;
            if (v[h][mid] >= k){
                res = mid;
                ri = mid - 1;
            }else{
                le = mid + 1;
            }
        }
        if (res == -1) return 0;
        return (int)v[h].size() - res;
    }
    return get(left,L,R,k) + get(right,L,R,k);
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,q;
    cin>>n>>q;

    vector <int> v1;
    vector <pair<pii,int> > vec;
    for (int i = 1; i <= n; i++){
        cin >> S[i] >> T[i];
        v1.pb(S[i]);
        vec.pb({{S[i] + T[i],2},i});
    }

    for (int i = 1; i <= q; i++){
        cin >> X[i] >> Y[i] >> Z[i];
        v1.pb(X[i]);
        vec.pb({{Z[i],1},i});
    }

    sort(vec.begin(),vec.end());
    sort(v1.begin(),v1.end());

    int val = 0;
    for (int i=0;i<v1.size();i++){
        if (!i || v1[i] != v1[i - 1]) ++val;
        mp[v1[i]] = val;
    }

    for (int i=vec.size()-1;i>=0;i--){
        int id = vec[i].s;
        if (vec[i].f.s == 2){
            upd(1,1,n + q,mp[S[id]],T[id]);
        }else{
            ans[id] = get(1,1,n + q,mp[X[id]],n + q,Y[id]);
        }
    }
    for (int i = 1; i <= q; i++)
        cout<<ans[i]<<endl;
}

Compilation message

examination.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
examination.cpp:25:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if (l1 == x.size()){
      |             ~~~^~~~~~~~~~~
examination.cpp:29:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if (l2 == y.size()){
      |             ~~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:110:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0;i<v1.size();i++){
      |                  ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12936 KB Output is correct
7 Correct 54 ms 14392 KB Output is correct
8 Correct 57 ms 14444 KB Output is correct
9 Correct 53 ms 14380 KB Output is correct
10 Correct 34 ms 14392 KB Output is correct
11 Correct 62 ms 14148 KB Output is correct
12 Correct 45 ms 14120 KB Output is correct
13 Correct 54 ms 14440 KB Output is correct
14 Correct 54 ms 14384 KB Output is correct
15 Correct 54 ms 14384 KB Output is correct
16 Correct 29 ms 14096 KB Output is correct
17 Correct 33 ms 14416 KB Output is correct
18 Correct 36 ms 14104 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12936 KB Output is correct
7 Correct 54 ms 14392 KB Output is correct
8 Correct 57 ms 14444 KB Output is correct
9 Correct 53 ms 14380 KB Output is correct
10 Correct 34 ms 14392 KB Output is correct
11 Correct 62 ms 14148 KB Output is correct
12 Correct 45 ms 14120 KB Output is correct
13 Correct 54 ms 14440 KB Output is correct
14 Correct 54 ms 14384 KB Output is correct
15 Correct 54 ms 14384 KB Output is correct
16 Correct 29 ms 14096 KB Output is correct
17 Correct 33 ms 14416 KB Output is correct
18 Correct 36 ms 14104 KB Output is correct
19 Execution timed out 3091 ms 37280 KB Time limit exceeded
20 Halted 0 ms 0 KB -