제출 #886337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886337		Kutan	Measures (CEOI22_measures)	C++14	100 / 100	238 ms	29968 KiB

Main

// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));

const int INF = 1e9 , mod = 1e9 + 7;

template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }

template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }

template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }

template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }

#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}

typedef long long ll;
typedef double db;
const int N = 2e5 + 50;

int n, m;
ll a[N], d, b[N];

void readip(){
    cin >> n >> m >> d; 
    REP(i, 1, n) cin >> a[i], a[i] *= 2LL;
}

namespace sub12{
    bool check(ll D) {
        ll f = -1e18;   
        REP(i, 1, n) {
            if (a[i] <= f) {
                if (f - a[i] > D) return 0;
                else f += d;
            }
            else {
                ll tmp = max(f, a[i] - D);
                f = tmp + d;
            }
        }
        return 1;
    }

    void solve() {
        d *= 2LL;
        REP(i, 1, m) {
            cin >> a[++n]; a[n] *= 2;
            sort(a + 1, a + n + 1);
            ll res = 1e18, l = 0, r = 1LL * (n - 1) * d;
            while(l <= r) {
                ll mid = (l + r) >> 1;
                if (check(mid)) res = mid, r = mid - 1;
                else l = mid + 1;
            }
            cout << res / 2; 
            if (res & 1) cout << ".5";
            cout << ' ';
        }
    }
};

namespace sub4 {
    struct Fenwick{
        int fen[N] = {};
        void upd(int i, int inc) {
            for (; i <= m; i += i & -i) fen[i] += inc;
        }
        int get(int i) {
            int res(0); 
            for (; i > 0; i -= i & -i) res += fen[i];
            return res;
        }
    } Fen;

    struct segtree{
        struct Node{
            ll Max, Min, lz;
            Node() {
                Max = -1e18, Min = 1e18;
                lz = 0;
            }

            void inc(ll val) {
                Max += val;
                Min += val;
                lz += val;
            }
        } it[N << 2];

        void down(int id) {
            ll &lz = it[id].lz;
            if (!lz) return;
            it[id << 1].inc(lz);
            it[id << 1 | 1].inc(lz);
            lz = 0;
        }

        void update(int u, int v, ll val, int id = 1, int l = 1, int r = m) {
            if (u <= l && r <= v)  {
                it[id].inc(val);
                return;
            }
            int mid = (l + r) >> 1;
            down(id);
            if (u <= mid) update(u, v, val, id << 1, l, mid);
            if (v > mid) update(u, v, val, id << 1 | 1, mid + 1, r);
            it[id].Max = max(it[id << 1].Max, it[id << 1 | 1].Max);
            it[id].Min = min(it[id << 1].Min, it[id << 1 | 1].Min);
        }

        void upd(int u, ll val, int id = 1, int l = 1, int r = m) {
            if (l == r) {
                it[id].Min = it[id].Max = val;
                return;
            }
            down(id);
            int mid = (l + r) >> 1;
            if (u <= mid) upd(u, val, id << 1, l, mid);
            else upd(u, val, id << 1 | 1, mid + 1, r);
            it[id].Max = max(it[id << 1].Max, it[id << 1 | 1].Max);
            it[id].Min = min(it[id << 1].Min, it[id << 1 | 1].Min);
        }  

        ll getMax(int u, int v, int id = 1, int l = 1, int r = m) {
            if (u <= l && r <= v) return it[id].Max;
            int mid = (l + r) >> 1;
            down(id);
            ll res = -1e18;
            if (u <= mid) maximize(res, getMax(u, v, id << 1, l, mid));
            if (v > mid) maximize(res, getMax(u, v, id << 1 | 1, mid + 1, r));
            return res;
        }

        ll getMin(int u, int v, int id = 1, int l = 1, int r = m) {
            if (u <= l && r <= v) return it[id].Min;
            down(id);
            int mid = (l + r) >> 1;
            ll res = 1e18;
            if (u <= mid) minimize(res, getMin(u, v, id << 1, l, mid));
            if (v > mid) minimize(res, getMin(u, v, id << 1 | 1, mid + 1, r));
            return res;
        }
    } ST;

    int idx[N];
    void solve() {
        vpii vec;
        REP(i, 1, m) vec.eb(b[i], i);
        sort(ALL(vec));
        FOR(i, vec.size()) idx[vec[i].se] = i+1;

        ll res = 0;
        REP(i, 1, m) {
            int id = idx[i];
            Fen.upd(id, +1);
            int stt = Fen.get(id);

            ll val = b[i] - 1LL * d * stt;
            ll MaxLef = -1e18, MinRig = 1e18;
            if (id > 1) MaxLef = ST.getMax(1, id - 1);
            if (id < m) {
                ST.update(id + 1, m, -d);
                MinRig = ST.getMin(id + 1, m);
            }   
            maximize(res, MaxLef - val);
            maximize(res, val - MinRig);
            maximize(res, MaxLef - MinRig);
            ST.upd(id, val);
            cout << res/2;
            if (res & 1) cout << ".5";
            cout << ' ';
        }
    }   
}; 

void solve(){   
    if (m <= 10) {
        sub12::solve();
        return;
    }
    REP(i, 1, m) cin >> b[i];
    sub4::solve();
}   

int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

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

Main.cpp: In function 'void readip()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:144:5: note: in expansion of macro 'REP'
  144 |     REP(i, 1, n) cin >> a[i], a[i] *= 2LL;
      |     ^~~
Main.cpp: In function 'bool sub12::check(ll)':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:150:9: note: in expansion of macro 'REP'
  150 |         REP(i, 1, n) {
      |         ^~~
Main.cpp: In function 'void sub12::solve()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:165:9: note: in expansion of macro 'REP'
  165 |         REP(i, 1, m) {
      |         ^~~
Main.cpp: In function 'void sub4::solve()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:267:9: note: in expansion of macro 'REP'
  267 |         REP(i, 1, m) vec.eb(b[i], i);
      |         ^~~
Main.cpp:94:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   94 | #define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
Main.cpp:269:9: note: in expansion of macro 'FOR'
  269 |         FOR(i, vec.size()) idx[vec[i].se] = i+1;
      |         ^~~
Main.cpp:94:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 | #define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                                     ~~~~^~~~~
Main.cpp:269:9: note: in expansion of macro 'FOR'
  269 |         FOR(i, vec.size()) idx[vec[i].se] = i+1;
      |         ^~~
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:272:9: note: in expansion of macro 'REP'
  272 |         REP(i, 1, m) {
      |         ^~~
Main.cpp: In function 'void solve()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:300:5: note: in expansion of macro 'REP'
  300 |     REP(i, 1, m) cin >> b[i];
      |     ^~~
Main.cpp: In function 'void file()':
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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