Submission #935945

#	Time	Username	Problem	Language	Result	Execution time	Memory
935945		Ludissey	Measures (CEOI22_measures)	C++14	35 / 100	202 ms	30544 KiB

Main

#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
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 0 / 41