oj.uz

Submission #935945

# Submission time Handle Problem Language Result Execution time Memory
935945 2024-02-29T19:39:10 Z Ludissey Measures (CEOI22_measures) C++14
35 / 100
 202 ms 30544 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
 
struct Node {
    Node *left;
    Node *right;
    int mn,mx;
    Node() : left(NULL), right(NULL), mn(), mx() {};
};

Node *NODE;

void build(Node* root, int l, int r){
    if(l==r) {
        root->mx=-1e18;
        root->mn=1e18;
        return;
    }
    int mid=(l+r)/2;
    root->left=new Node;
    root->right=new Node;
    build(root->left,l,mid);
    build(root->right,mid+1,r);
    root->mx=max(root->left->mx, root->right->mx);
    root->mn=min(root->left->mn, root->right->mn);
}

pair<int,int> minmax(Node* root, int l, int r, int ql, int qr){
    if(qr<l||ql>r) return {1e18, -1e18};
    if(ql<=l&&r<=qr){
        return {root->mn, root->mx};
    }
    int mid=(l+r)/2;
    pair<int,int> a,b;
    a=minmax(root->left,l,mid,ql,qr);
    b=minmax(root->right,mid+1,r,ql,qr);
    return {min(a.first,b.first), max(a.second,b.second)};
}
void update(Node* root, int l, int r, int p, int v){
   if(r<p||l>p) return;
    if(l==p&&r==p){
        root->mn=v;
        root->mx=v;
        return;
    }
    int mid=(l+r)/2;
    update(root->left,l,mid,p,v);
    update(root->right,mid+1,r,p,v);
    root->mx=max(root->left->mx, root->right->mx);
    root->mn=min(root->left->mn, root->right->mn);
}
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,m,D; cin >> n >> m >> D;
    NODE=new Node;
    vector<pair<int,int>> asort(m);
    vector<pair<int,int>> a(m);
    for (int i = 0; i < m; i++)
    {
        cin >> a[i].first;
        asort[i]={a[i].first,i};
    }
    sort(asort.begin(),asort.end());
    for (int i = 0; i < m; i++) a[asort[i].second].second=i;
    build(NODE, 0, m-1);
    int retMax=0;
    for (int _i = 0; _i < m; _i++)
    {
        int x=a[_i].first;
        int cmin=minmax(NODE, 0, m-1, 0, a[_i].second-1).first;
        int cmax=minmax(NODE, 0, m-1, a[_i].second+1, m-1).second;
        retMax=max(max(((_i*D)-x)-cmin, cmax-((_i*D)-x)), retMax);
        if(retMax%2==0) cout << retMax/2LL << " ";
        else cout << retMax/2LL << ".5 ";
        update(NODE, 0, m-1, a[_i].second, ((_i*D)-x));
    }
    cout << "\n";
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 123 ms 28364 KB Output is correct
2 Correct 127 ms 30292 KB Output is correct
3 Correct 137 ms 30268 KB Output is correct
4 Correct 136 ms 27984 KB Output is correct
5 Correct 124 ms 29352 KB Output is correct
6 Correct 128 ms 28500 KB Output is correct
7 Correct 128 ms 29500 KB Output is correct
8 Correct 121 ms 28116 KB Output is correct
9 Correct 132 ms 27988 KB Output is correct
10 Correct 126 ms 30544 KB Output is correct
11 Correct 121 ms 28904 KB Output is correct
12 Correct 127 ms 30024 KB Output is correct
13 Correct 120 ms 27988 KB Output is correct
14 Correct 125 ms 30032 KB Output is correct
15 Correct 126 ms 29868 KB Output is correct
16 Correct 117 ms 27804 KB Output is correct
17 Correct 125 ms 29356 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 28364 KB Output is correct
2 Correct 127 ms 30292 KB Output is correct
3 Correct 137 ms 30268 KB Output is correct
4 Correct 136 ms 27984 KB Output is correct
5 Correct 124 ms 29352 KB Output is correct
6 Correct 128 ms 28500 KB Output is correct
7 Correct 128 ms 29500 KB Output is correct
8 Correct 121 ms 28116 KB Output is correct
9 Correct 132 ms 27988 KB Output is correct
10 Correct 126 ms 30544 KB Output is correct
11 Correct 121 ms 28904 KB Output is correct
12 Correct 127 ms 30024 KB Output is correct
13 Correct 120 ms 27988 KB Output is correct
14 Correct 125 ms 30032 KB Output is correct
15 Correct 126 ms 29868 KB Output is correct
16 Correct 117 ms 27804 KB Output is correct
17 Correct 125 ms 29356 KB Output is correct
18 Incorrect 202 ms 29264 KB Output isn't correct
19 Halted 0 ms 0 KB -