Submission #1111499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111499		koukirocks	Measures (CEOI22_measures)	C++17	100 / 100	495 ms	69632 KiB

Main

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

struct link{
    ll x,l,r;
    link(ll x):x(x),l(0),r(0) {}
};

struct Node{
    ll ans,pl,pr,sum;
    ll l,r;
    Node *lft,*rt;
    void pu() {
        sum=lft->sum+rt->sum;
        pl=max(lft->pl,lft->sum+rt->pl);
        pr=max(rt->pr,rt->sum+lft->pr);
        ans=max({lft->ans,rt->ans,lft->pr+rt->pl});
    }
    Node(int l,int r,vector<ll> &dif):l(l),r(r),lft(nullptr),rt(nullptr) {
        if (l==r) {
            sum=dif[l];
            pl=max(0ll,dif[l]);
            pr=max(0ll,dif[l]);
            ans=max(0ll,dif[l]);
            return;
        }
        int mid=l+r>>1;
        lft = new Node(l,mid,dif);
        rt = new Node(mid+1,r,dif);
        pu();
        // cout<<l<<" "<<r<<" "<<sum<<" "<<pl<<" "<<pr<<" "<<ans<<" l r sum pl pr ans\n";
    }
    void update(int tar,ll val) {
        if (l==r) {
            sum=val;
            pl=max(0ll,val);
            pr=max(0ll,val);
            ans=max(0ll,val);
            return;
        }
        int mid=l+r>>1;
        if (tar<=mid) lft->update(tar,val);
        else rt->update(tar,val);
        pu();
    }
    void pt() {
        cout<<l<<" "<<r<<" "<<sum<<" "<<pl<<" "<<pr<<" "<<ans<<" l r sum pl pr ans\n";
        if (lft) lft->pt();
        if (rt) rt->pt();
    }
};

int main() {
    speed;
    ll n,m,d;
    cin>>n>>m>>d;
    vector<link> pos;
    vector<ll> pm(m);
    for (int i=0;i<n;i++) {
        ll x;
        cin>>x;
        pos.push_back(link(x));
    }
    for (int i=0;i<m;i++) {
        cin>>pm[i];
        pos.push_back(link(pm[i]));
    }
    map<ll,vector<int>> vtp;
    sort(all(pos),[&](link a,link b) {
        return a.x<b.x;
    });
    int tn=pos.size();
    for (int i=0;i<tn;i++) {
        vtp[pos[i].x].push_back(i);
        pos[i].l=i-1;
        pos[i].r=i+1;
    }
    vector<ll> dif(tn);
    for (int i=1;i<tn;i++) {
        dif[i]=d-(pos[i].x-pos[i-1].x);
    }
    Node *rt = new Node(1,tn-1,dif);
    vector<ll> ans(m);
    for (int i=m-1;i>=0;i--) {
        ans[i]=rt->ans;
        ll dp = vtp[pm[i]].back();
        vtp[pm[i]].pop_back();
        rt->update(dp,0);
        ll pr=pos[dp].r,pl=pos[dp].l;
        if (pr!=tn and pl!=-1) {
            rt->update(pr,d-(pos[pr].x-pos[pl].x));
        } else if (pl==-1) rt->update(pr,0);
        if (pr!=tn) pos[pr].l=pl;
        if (pl!=-1) pos[pl].r=pr;
        // cout<<i<<" "<<dp<<" i\n";
        // rt->pt();
    }
    for (int i=0;i<m;i++) {
        if (ans[i]&1) cout<<ans[i]/2<<".5 ";
        else cout<<ans[i]/2<<" ";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'Node::Node(int, int, std::vector<long long int>&)':
Main.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'void Node::update(int, ll)':
Main.cpp:63:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid=l+r>>1;
      |                 ~^~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41