oj.uz

Submission #831910

# Submission time Handle Problem Language Result Execution time Memory
831910 2023-08-20T17:30:14 Z QwertyPi Measures (CEOI22_measures) C++14
35 / 100
 285 ms 43032 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e5 + 11;

int n, m, d;

struct node{
    bool active; int _min, _max, _diff, lazy;
    node(): active(0), _min(0), _max(0), _diff(0), lazy(0){};
    node(int v) : active(1), _min(v), _max(v), _diff(0), lazy(0){};
    int get_diff(){ return _diff; }
};

node operator+ (const node& a, const node& b){
    if(!a.active || !b.active) return a.active ? a : b;
    node res;
    res.active = true;
    res._min = min(a._min, b._min);
    res._max = max(a._max, b._max);
    res._diff = max(max(a._diff, b._diff), a._max - b._min);
    return res;
}

void operator+= (node& a, int x){
    a._min += x;
    a._max += x;
    a.lazy += x;
}

node t[MAXN << 2];

void st_push(int v){
    t[v * 2 + 1] += t[v].lazy;
    t[v * 2 + 2] += t[v].lazy;
    t[v].lazy = 0;
}

void st_range_add(int ql, int qr, int qv, int v = 0, int l = 0, int r = MAXN - 1){
    if(qr < l || r < ql) return;
    if(ql <= l && r <= qr) t[v] += qv;
    else {
        st_push(v);
        int m = (l + r) / 2;
        st_range_add(ql, qr, qv, v * 2 + 1, l, m);
        st_range_add(ql, qr, qv, v * 2 + 2, m + 1, r);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }
}

void st_point_add(int qi, int qv, int v = 0, int l = 0, int r = MAXN - 1){
    if(l == r) t[v] = node(t[v]._min + qv);
    else {
        st_push(v);
        int m = (l + r) / 2;
        if(qi <= m) st_point_add(qi, qv, v * 2 + 1, l, m);
        else st_point_add(qi, qv, v * 2 + 2, m + 1, r);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }
}

int st_point_qry(int qi, int v = 0, int l = 0, int r = MAXN - 1){
    if(l == r) return t[v]._max;
    int m = (l + r) / 2;
    if(qi <= m) return st_point_qry(qi, v * 2 + 1, l, m);
    else return st_point_qry(qi, v * 2 + 2, m + 1, r);
}

void add(int x, int v){
    st_range_add(x, MAXN - 1, -d);
    st_point_add(x, v);
}

int qry(){
    return t[0].get_diff();
}

int solve(vector<int>& a){
    vector<int> x;
    for(int i = 0; i < a.size(); i++){
        x.push_back(a[i] - i * d);
    }
    int mx = 0;
    for(int i = 0; i < x.size(); i++){
        for(int j = i; j < x.size(); j++){
            mx = max(mx, x[i] - x[j]);
        }
    }
    return mx;
}

int32_t main(){
    cin >> n >> m >> d;
    vector<int> a, b, ai, bi;
    for(int i = 0; i < n; i++) { 
        int v; cin >> v; a.push_back(v);
    }
    for(int i = 0; i < m; i++){
        int v; cin >> v; b.push_back(v);
    }
    vector<pair<int, int>> vp;
    for(int i = 0; i < n; i++){
        vp.push_back({a[i], i});
    }
    for(int i = 0; i < m; i++){
        vp.push_back({b[i], n + i});
    }
    sort(vp.begin(), vp.end());
    ai.resize(n); bi.resize(m);
    for(int i = 0; i < n + m; i++){
        if(vp[i].second < n){
            ai[vp[i].second] = i;
        }else{
            bi[vp[i].second - n] = i;
        }
    }
    for(int i = 0; i < n; i++){
        add(ai[i], a[i]);
    }
    for(int i = 0; i < m; i++){
        add(bi[i], b[i]);
        int ans = qry();
        cout << ans / 2 << (ans % 2 ? ".5" : "") << ' ';
    }
    cout << '\n';
}

Compilation message

Main.cpp: In function 'long long int solve(std::vector<long long int>&)':
Main.cpp:81:22: 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]
   81 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp:85:22: 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]
   85 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp:86:26: 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]
   86 |         for(int j = i; j < x.size(); j++){
      |                        ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 31624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 31624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 40840 KB Output is correct
2 Correct 193 ms 42676 KB Output is correct
3 Correct 200 ms 42676 KB Output is correct
4 Correct 187 ms 40608 KB Output is correct
5 Correct 189 ms 41768 KB Output is correct
6 Correct 194 ms 40928 KB Output is correct
7 Correct 200 ms 41856 KB Output is correct
8 Correct 192 ms 40560 KB Output is correct
9 Correct 213 ms 40516 KB Output is correct
10 Correct 195 ms 43032 KB Output is correct
11 Correct 189 ms 41408 KB Output is correct
12 Correct 191 ms 42352 KB Output is correct
13 Correct 188 ms 40572 KB Output is correct
14 Correct 240 ms 42544 KB Output is correct
15 Correct 196 ms 42272 KB Output is correct
16 Correct 180 ms 40148 KB Output is correct
17 Correct 206 ms 41844 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 40840 KB Output is correct
2 Correct 193 ms 42676 KB Output is correct
3 Correct 200 ms 42676 KB Output is correct
4 Correct 187 ms 40608 KB Output is correct
5 Correct 189 ms 41768 KB Output is correct
6 Correct 194 ms 40928 KB Output is correct
7 Correct 200 ms 41856 KB Output is correct
8 Correct 192 ms 40560 KB Output is correct
9 Correct 213 ms 40516 KB Output is correct
10 Correct 195 ms 43032 KB Output is correct
11 Correct 189 ms 41408 KB Output is correct
12 Correct 191 ms 42352 KB Output is correct
13 Correct 188 ms 40572 KB Output is correct
14 Correct 240 ms 42544 KB Output is correct
15 Correct 196 ms 42272 KB Output is correct
16 Correct 180 ms 40148 KB Output is correct
17 Correct 206 ms 41844 KB Output is correct
18 Incorrect 285 ms 42324 KB Output isn't correct
19 Halted 0 ms 0 KB -