Submission #782590

#	Time	Username	Problem	Language	Result	Execution time	Memory
782590		makanhulia	Strange Device (APIO19_strange_device)	C++17	0 / 100	1 ms	212 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

void solve() {
    int n, k, c, p; cin >> n >> k >> c >> p;
    
    int in[n+5];
    int out[n+5];

    for(int i = 1; i<=n; i++) cin >> in[i];
    for(int i = 1; i<=n; i++) cin >> out[i];

    if(p == 1) {
        int pref[n+5]; pref[0] = INT_MAX;
        int suf[n+5]; suf[n+1] = INT_MAX;

        for(int i = 1; i<=n; i++) pref[i] = min(pref[i-1], out[i]+c*(n-i-1));
        for(int i = n; i>=1; i--) suf[i] = min(suf[i+1], out[i]+(i-1)*c);
        // for(int i = 1; i<=n; i++) cerr << pref[i] << " "; cerr << endl;
        // for(int i = 1; i<=n; i++) cerr << suf[i] << " "; cerr << endl;

        for(int i = 1; i<=n; i++) {
            int x = k-in[i];

            int lo = i;
            int hi = n;
            int res = i-1;
            int money = x+(i-1)*c;

            while(lo <= hi) {
                int mid = (lo+hi)/2;

                if(suf[mid] <= money) lo = mid+1, res = mid;
                else hi = mid-1;
            }

            int lo2 = 1;
            int hi2 = i;
            int res2 = i+1;
            int money2 = x+(n-i-1)*c;
            while(lo2 <= hi2) {
                int mid = (lo2+hi2)/2;
                if(pref[mid] <= money2) hi2 = mid-1, res2 = mid;
                else lo2 = mid+1;
            }

            int lenl = i-res2+1;
            int lenr = res-i+1;
            int leftl = k-(in[i]+out[res2]+abs(i-res2)*c);
            int leftr = k-(in[i]+out[res]+abs(i-res)*c);

            // cerr << money << " " << money2 << endl;
            // cerr << res2 << " " << res << " " << lenl << " " << lenr << " " << leftl << " " << leftr << endl;
            // cerr << x << endl;

            if((!lenl && !lenr) || x < 0) {
                cout << "0 " << k << endl; 
            }
            else if(lenl == lenr) cout << lenl << " " << max(leftl, leftr) << endl;
            else if(lenl > lenr) cout << lenl << " " << leftl << endl;
            else cout << lenr << " " << leftr << endl;
        }
    }
    else {
        for(int i = 1; i<=n; i++) {
            int len = sqrt((double)(k-in[i])/c);

            int l = max(1ll, i-len);
            int r = min(n, len+i);

            // cerr << i << " " << len << " " << l << " " << r << " " << endl;

            int ansl = 0, ansr = 0;
            int leftl = k, leftr = k;

            int x = 1e3+1;

            for(int j = l; x && j != i; x--, j++) {
                int val = in[i]+out[j]+abs(i-j)*abs(i-j)*c;
                if(val <= k) {
                    ansl = abs(i-j)+1;
                    leftl = k-val;
                    break;
                }
            } 

            x = 1e3+1;
            for(int j = r; x && j != i; x--, j--) {
                int val = in[i]+out[j]+abs(i-j)*abs(i-j)*c;
                if(val <= k) {
                    ansr = abs(i-j)+1;
                    leftr = k-val;
                    break;
                }
            }

            if(ansl == ansr) cout << ansl << " " << max(leftl, leftr) << endl;
            else if(ansl > ansr) cout << ansl << " " << leftl << endl;
            else cout<< ansr << " " << leftr << endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

// (j-i) <= len

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30