oj.uz

Submission #951805

# Submission time Handle Problem Language Result Execution time Memory
951805 2024-03-22T16:52:01 Z Vladth11 Measures (CEOI22_measures) C++14
0 / 100
 228 ms 30940 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 400001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;

int d, cnt;

int lazy[NMAX * 4];
vector <pii> tot;

struct elem{
    int val, nrm;
}a[NMAX], b[NMAX];

bool cmp(pii aa, pii bb){
    int prim = a[aa.first].val;
    if(aa.second == 1)
        prim = b[aa.first].val;
    int sec = a[bb.first].val;
    if(bb.second == 1)
        sec = b[bb.first].val;
    return prim < sec;
}

struct Node {
    int maxim, minim;
    int sol;
} aint[NMAX * 4];

void propaga(int node, int st, int dr) {
    if(st != dr) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    aint[node].maxim += lazy[node];
    aint[node].minim += lazy[node];
    lazy[node] = 0;
}

Node combine(Node a, Node b) {
    Node sol = {-INF, INF, 0};
    sol.sol = max(a.sol, b.sol);
    sol.sol = max(sol.sol, a.maxim - b.minim);
    sol.maxim = max(a.maxim, b.maxim);
    sol.minim = min(a.minim, b.minim);
    return sol;
}

void activate(int node, int st, int dr, int x, int val) {
    propaga(node, st, dr);
    if(st == dr) {
        aint[node].maxim += INF + val;
        aint[node].minim -= INF;
        aint[node].minim += val;
        aint[node].sol = 0;
        return;
    }
    int mid = (st + dr) / 2;
    if(x <= mid)
        activate(node * 2, st, mid, x, val);
    else
        activate(node * 2 + 1, mid + 1, dr, x, val);
    propaga(node * 2, st, mid);
    propaga(node * 2 + 1, mid + 1, dr);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}

void update(int node, int st, int dr, int a, int b, int val) {
    if(a > dr)
        return;
    propaga(node, st, dr);
    if(a <= st && dr <= b) {
        lazy[node] += val;
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b, val);
    if(b > mid)
        update(node * 2 + 1, mid + 1, dr, a, b, val);
    propaga(node * 2, st, mid);
    propaga(node * 2 + 1, mid + 1, dr);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < NMAX * 4; i++) {
        aint[i].maxim = -INF;
        aint[i].minim = INF;
        aint[i].sol = 0;
    }
    int n, i, m, x;
    cin >> n >> m >> d;
    tot.clear();
    for(i = 1; i <= n; i++) {
        cin >> a[i].val;
        tot.push_back({i, 0});
    }
    for(i = 1; i <= m; i++) {
        cin >> b[i].val;
        tot.push_back({i, 1});
    }
    sort(tot.begin(), tot.end(), cmp);
    for(int i = 0; i < tot.size(); i++){
        if(tot[i].second == 1){
            b[tot[i].first].nrm = i + 1;
        }else{
            a[tot[i].first].nrm = i + 1;
        }
    }
    cnt = tot.size();
    for(i = 1; i <= n; i++) {
        update(1, 1, cnt, a[i].nrm + 1, cnt, -d);
        activate(1, 1, cnt, a[i].nrm, a[i].val);
    }
    for(i = 1; i <= m; i++) {
        update(1, 1, cnt, b[i].nrm + 1, cnt, -d);
        activate(1, 1, cnt, b[i].nrm, b[i].val);
        propaga(1, 1, cnt);
        int sol = max(0, aint[1].sol);
        cout << sol/2;
        if(sol%2) cout << ".5";
        cout << " ";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i = 0; i < tot.size(); i++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:108:18: warning: unused variable 'x' [-Wunused-variable]
  108 |     int n, i, m, x;
      |                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB Output is correct
2 Correct 7 ms 25176 KB Output is correct
3 Correct 7 ms 25436 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 7 ms 25236 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Incorrect 6 ms 25176 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB Output is correct
2 Correct 7 ms 25176 KB Output is correct
3 Correct 7 ms 25436 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 7 ms 25236 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Incorrect 6 ms 25176 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 27916 KB Output is correct
2 Incorrect 228 ms 30940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 27916 KB Output is correct
2 Incorrect 228 ms 30940 KB Output isn't correct
3 Halted 0 ms 0 KB -