제출 #937074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937074		Ludissey	Measures (CEOI22_measures)	C++14	100 / 100	391 ms	36180 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,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;
}

컴파일 시 표준 에러 (stderr) 메시지

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