oj.uz

Submission #937074

# Submission time Handle Problem Language Result Execution time Memory
937074 2024-03-03T11:11:56 Z Ludissey Measures (CEOI22_measures) C++14
100 / 100
 391 ms 36180 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>0){
        if(root->left) root->left->lazy+=root->lazy;
        if(root->right) 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){
    propagate(root);
    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){
    propagate(root);
    if(r<p||l>p) return;
    if(l==p&&r==p){
        root->mn=v;
        root->mx=v;
        root->children=1;
        return;
    }
    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++;
        propagate(root);
        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;
    if(n==0){
        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";
    }else{
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int _i = 0; _i < m; _i++)
        {
            int x; cin >> x;
            a.push_back(x);
            sort(a.begin(),a.end());
            double l=0,r=2000000000000000;
            double ans=0;
            while(r-l>=0.1){
                double mid=(l+r)/(double)2;
                double lb=a[0]-mid;
                bool br=false;
                for (int i = 1; i < a.size(); i++)
                {
                    double bc=max(lb+(double)D, (double)a[i]-mid);
                    if(bc>(double)a[i]+mid) {
                        br=true;
                        break;
                    }
                    lb=bc;
                }
                if(br){
                    l=mid;
                }else{
                    ans=mid;
                    r=mid;
                }
            }
            int roundAns=ans;
    
            if((double)ans-roundAns<0.25) cout << roundAns << " ";
            else if ((double)ans-roundAns<0.75) cout << roundAns << ".5 ";
            else cout << roundAns+1 << " ";
    
        }
        cout << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:138:35: 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]
  138 |                 for (int i = 1; i < a.size(); i++)
      |                                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 516 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 516 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 335 ms 5460 KB Output is correct
10 Correct 382 ms 6116 KB Output is correct
11 Correct 281 ms 6736 KB Output is correct
12 Correct 391 ms 5456 KB Output is correct
13 Correct 287 ms 5716 KB Output is correct
14 Correct 323 ms 5340 KB Output is correct
15 Correct 342 ms 5728 KB Output is correct
16 Correct 286 ms 5468 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 33872 KB Output is correct
2 Correct 214 ms 35776 KB Output is correct
3 Correct 256 ms 35668 KB Output is correct
4 Correct 205 ms 34044 KB Output is correct
5 Correct 207 ms 34936 KB Output is correct
6 Correct 207 ms 33936 KB Output is correct
7 Correct 218 ms 34808 KB Output is correct
8 Correct 201 ms 33784 KB Output is correct
9 Correct 206 ms 33624 KB Output is correct
10 Correct 213 ms 36068 KB Output is correct
11 Correct 205 ms 34384 KB Output is correct
12 Correct 206 ms 35412 KB Output is correct
13 Correct 208 ms 33616 KB Output is correct
14 Correct 226 ms 35924 KB Output is correct
15 Correct 207 ms 35368 KB Output is correct
16 Correct 234 ms 33360 KB Output is correct
17 Correct 207 ms 34956 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 33872 KB Output is correct
2 Correct 214 ms 35776 KB Output is correct
3 Correct 256 ms 35668 KB Output is correct
4 Correct 205 ms 34044 KB Output is correct
5 Correct 207 ms 34936 KB Output is correct
6 Correct 207 ms 33936 KB Output is correct
7 Correct 218 ms 34808 KB Output is correct
8 Correct 201 ms 33784 KB Output is correct
9 Correct 206 ms 33624 KB Output is correct
10 Correct 213 ms 36068 KB Output is correct
11 Correct 205 ms 34384 KB Output is correct
12 Correct 206 ms 35412 KB Output is correct
13 Correct 208 ms 33616 KB Output is correct
14 Correct 226 ms 35924 KB Output is correct
15 Correct 207 ms 35368 KB Output is correct
16 Correct 234 ms 33360 KB Output is correct
17 Correct 207 ms 34956 KB Output is correct
18 Correct 317 ms 34004 KB Output is correct
19 Correct 344 ms 35940 KB Output is correct
20 Correct 211 ms 35732 KB Output is correct
21 Correct 274 ms 33800 KB Output is correct
22 Correct 269 ms 34128 KB Output is correct
23 Correct 264 ms 34020 KB Output is correct
24 Correct 330 ms 34644 KB Output is correct
25 Correct 224 ms 33912 KB Output is correct
26 Correct 316 ms 33620 KB Output is correct
27 Correct 353 ms 36180 KB Output is correct
28 Correct 289 ms 34132 KB Output is correct
29 Correct 319 ms 35440 KB Output is correct
30 Correct 239 ms 33616 KB Output is correct
31 Correct 247 ms 35920 KB Output is correct
32 Correct 223 ms 35596 KB Output is correct
33 Correct 330 ms 33360 KB Output is correct
34 Correct 243 ms 35124 KB Output is correct