oj.uz

Submission #1111499

# Submission time Handle Problem Language Result Execution time Memory
1111499 2024-11-12T08:55:19 Z koukirocks Measures (CEOI22_measures) C++17
100 / 100
 495 ms 69632 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 109 ms 63200 KB Output is correct
10 Correct 108 ms 63200 KB Output is correct
11 Correct 52 ms 42160 KB Output is correct
12 Correct 120 ms 63148 KB Output is correct
13 Correct 94 ms 62720 KB Output is correct
14 Correct 97 ms 63096 KB Output is correct
15 Correct 100 ms 62636 KB Output is correct
16 Correct 97 ms 63276 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 65400 KB Output is correct
2 Correct 177 ms 67184 KB Output is correct
3 Correct 98 ms 48044 KB Output is correct
4 Correct 191 ms 67244 KB Output is correct
5 Correct 186 ms 68536 KB Output is correct
6 Correct 181 ms 67560 KB Output is correct
7 Correct 172 ms 68524 KB Output is correct
8 Correct 182 ms 67244 KB Output is correct
9 Correct 176 ms 67080 KB Output is correct
10 Correct 186 ms 69548 KB Output is correct
11 Correct 191 ms 68016 KB Output is correct
12 Correct 183 ms 68812 KB Output is correct
13 Correct 181 ms 67256 KB Output is correct
14 Correct 190 ms 69036 KB Output is correct
15 Correct 185 ms 68788 KB Output is correct
16 Correct 181 ms 66732 KB Output is correct
17 Correct 179 ms 68356 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 65400 KB Output is correct
2 Correct 177 ms 67184 KB Output is correct
3 Correct 98 ms 48044 KB Output is correct
4 Correct 191 ms 67244 KB Output is correct
5 Correct 186 ms 68536 KB Output is correct
6 Correct 181 ms 67560 KB Output is correct
7 Correct 172 ms 68524 KB Output is correct
8 Correct 182 ms 67244 KB Output is correct
9 Correct 176 ms 67080 KB Output is correct
10 Correct 186 ms 69548 KB Output is correct
11 Correct 191 ms 68016 KB Output is correct
12 Correct 183 ms 68812 KB Output is correct
13 Correct 181 ms 67256 KB Output is correct
14 Correct 190 ms 69036 KB Output is correct
15 Correct 185 ms 68788 KB Output is correct
16 Correct 181 ms 66732 KB Output is correct
17 Correct 179 ms 68356 KB Output is correct
18 Correct 422 ms 67492 KB Output is correct
19 Correct 418 ms 69292 KB Output is correct
20 Correct 101 ms 48180 KB Output is correct
21 Correct 244 ms 67328 KB Output is correct
22 Correct 347 ms 67500 KB Output is correct
23 Correct 218 ms 67504 KB Output is correct
24 Correct 480 ms 68044 KB Output is correct
25 Correct 181 ms 66988 KB Output is correct
26 Correct 415 ms 66972 KB Output is correct
27 Correct 495 ms 69632 KB Output is correct
28 Correct 355 ms 67500 KB Output is correct
29 Correct 433 ms 68760 KB Output is correct
30 Correct 244 ms 66988 KB Output is correct
31 Correct 250 ms 69036 KB Output is correct
32 Correct 231 ms 68780 KB Output is correct
33 Correct 458 ms 66908 KB Output is correct
34 Correct 244 ms 68356 KB Output is correct