제출 #831944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831944		QwertyPi	Measures (CEOI22_measures)	C++14	100 / 100	336 ms	42964 KiB

Main

#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){
    node res;
    if(!a.active || !b.active){
        res = a.active ? a : b;
        res.lazy = 0;
        return 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);
    res.lazy = 0;
    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;
    st_push(v);
    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';
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41