oj.uz

Submission #1081693

# Submission time Handle Problem Language Result Execution time Memory
1081693 2024-08-30T09:17:12 Z vjudge1 Measures (CEOI22_measures) C++17
0 / 100
 31 ms 8528 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 998244353
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<pair<pair<int,int>,int>,null_type,less<pair<pair<int,int>,int>>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,d;
    cin>>n>>m>>d;
    if(!n){
        d*=2;
        deque<pair<int,int>>a,b;
        int tt=0,l=0,r=0,ans=0;
        while(m--){
            int x;
            cin>>x;
            x*=2;
            ans+=(a.size()?max(0ll,d-(x-a.back().first)):0);
            a.push_back({x,(a.size()?max(0ll,d-(x-a.back().first))+a.back().second:0)});
            if(b.size())tt+=max(0ll,d-(x-b.back().first));
            b.push_back({x,-tt});
            // cout<<ans<<' ';
            while(r+1<a.size()||l<r){
                if(l<r){
                    int k=max(a.back().second-a[r].second,(b[0].second)-(b[r].second));
                    // cout<<r<<' '<<b[0].second-b[r].second<<' ';
                    if(k<ans){
                        // cout<<'g';
                        ans=k;
                        l++;
                    }else break;
                }else{
                    int A=a.back().second-a[r+1].second,B=b[0].second-b[r].second;
                    int K=max(A,B)+max(0ll,(d-(a[r+1].first-a[r].first))-(max(A,B)-min(A,B)))/2;
                    // cout<<'f'<<K<<' '<<k<<'f';
                    if(K<ans){
                        // cout<<ans<<' '<<K;
                        ans=K;
                        // cout<<'f';
                        // cout<<'g'<<ans<<'g';
                        r++;
                    }else break;
                }
            }
            cout<<ans/2;
            if(ans&1)cout<<".5";
            cout<<' ';
        }
    }else{

    }
}
/*
1
13
7 10 13 |4 |5 10| 8| 3 6 5 |7 10| 2


*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:27:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             while(r+1<a.size()||l<r){
      |                   ~~~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 8528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 8528 KB Output isn't correct
2 Halted 0 ms 0 KB -