oj.uz

Submission #937066

# Submission time Handle Problem Language Result Execution time Memory
937066 2024-03-03T10:32:17 Z Ludissey Measures (CEOI22_measures) C++14
35 / 100
 287 ms 36860 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,lazy,children;
    Node() : left(NULL), right(NULL), mn(0), mx(0), lazy(0), children(0) {};
    void update(){
        mx=max(left->mx, right->mx);
        mn=min(left->mn, right->mn);
        children=left->children+right->children;
    }
};

Node *NODE;
int D;

void propagate(Node* root){
    if(root->lazy){
        root->left->lazy+=root->lazy;
        root->right->lazy+=root->lazy;
        root->mn+=D*root->lazy;
        root->mx+=D*root->lazy;
        root->lazy=0;
    }
}

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->update();
}

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)};
}
int kthPos(Node* root, int l, int r, int ql, int qr){
    if(qr<l||ql>r) return 0;
    if(ql<=l&&r<=qr){
        return root->children;
    }
    int mid=(l+r)/2;
    pair<int,int> a,b;
    return kthPos(root->left,l,mid,ql,qr)+kthPos(root->right,mid+1,r,ql,qr);
}

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;
        root->children=1;
        return;
    }
    propagate(root);
    int mid=(l+r)/2;
    update(root->left,l,mid,p,v);
    update(root->right,mid+1,r,p,v);
    root->update();
}

void updateLAZY(Node* root, int l, int r, int ql, int qr){
   if(r<ql||l>qr) return;
    if(l>=ql&&r<=qr){
        root->lazy++;
        root->mn+=D;
        root->mx+=D;
        return;
    }
    propagate(root);
    int mid=(l+r)/2;
    updateLAZY(root->left,l,mid,ql,qr);
    updateLAZY(root->right,mid+1,r,ql,qr);
    root->update();
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,m; 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;
        update(NODE, 0, m-1, a[_i].second, (kthPos(NODE, 0, m-1, 0, a[_i].second)*D)-x);
        updateLAZY(NODE, 0, m-1, a[_i].second+1, m-1);
        int cmin=minmax(NODE, 0, m-1, 0, a[_i].second).first;
        int cmax=minmax(NODE, 0, m-1, a[_i].second, m-1).second;
        retMax=max(cmax-cmin, retMax);
        if(retMax%2==0) cout << retMax/2LL << " ";
        else cout << retMax/2LL << ".5 ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 169 ms 34712 KB Output is correct
2 Correct 172 ms 36652 KB Output is correct
3 Correct 182 ms 36480 KB Output is correct
4 Correct 167 ms 34468 KB Output is correct
5 Correct 175 ms 35784 KB Output is correct
6 Correct 167 ms 35060 KB Output is correct
7 Correct 170 ms 35764 KB Output is correct
8 Correct 168 ms 34708 KB Output is correct
9 Correct 171 ms 34388 KB Output is correct
10 Correct 172 ms 36860 KB Output is correct
11 Correct 167 ms 35196 KB Output is correct
12 Correct 178 ms 36024 KB Output is correct
13 Correct 170 ms 34460 KB Output is correct
14 Correct 169 ms 36432 KB Output is correct
15 Correct 173 ms 36176 KB Output is correct
16 Correct 166 ms 33964 KB Output is correct
17 Correct 174 ms 35664 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 34712 KB Output is correct
2 Correct 172 ms 36652 KB Output is correct
3 Correct 182 ms 36480 KB Output is correct
4 Correct 167 ms 34468 KB Output is correct
5 Correct 175 ms 35784 KB Output is correct
6 Correct 167 ms 35060 KB Output is correct
7 Correct 170 ms 35764 KB Output is correct
8 Correct 168 ms 34708 KB Output is correct
9 Correct 171 ms 34388 KB Output is correct
10 Correct 172 ms 36860 KB Output is correct
11 Correct 167 ms 35196 KB Output is correct
12 Correct 178 ms 36024 KB Output is correct
13 Correct 170 ms 34460 KB Output is correct
14 Correct 169 ms 36432 KB Output is correct
15 Correct 173 ms 36176 KB Output is correct
16 Correct 166 ms 33964 KB Output is correct
17 Correct 174 ms 35664 KB Output is correct
18 Incorrect 287 ms 35764 KB Output isn't correct
19 Halted 0 ms 0 KB -