제출 #523532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523532		placik	Snowball (JOI21_ho_t2)	C++17	100 / 100	115 ms	16876 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define all(a) a.begin(),a.end()
#define sz(x) (ll)(x).size()
const int mxN = 2e5+7;
ll x[mxN],odp[mxN];
struct poz{
	ll lewo,prawo;
	ll suma;
	int kogo_ruch; //0 brak, 1 lewo, 2 prawo
};
poz t[mxN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,q,w; cin >> n >> q;
	rep(i,1,n) cin >> x[i];
	ll akt=0,mL=0,mP=0;
	rep(i,1,q){
		cin >> w;
		if(w > 0) t[i-1].kogo_ruch = 2;
		if(w < 0) t[i-1].kogo_ruch = 1;
		akt += w;
		mL = min(akt,mL);
		mP = max(akt,mP);
		t[i] = {mL,mP,mP-mL,0};
	}
	odp[1] -= mL;
	odp[n] += mP;
	rep(i,2,n){
		ll odl = x[i]-x[i-1];
		int p=0,k=q;
		while(p < k){
			int m = (p+k+1)/2;
			if(t[m].suma <= odl) p = m;
			else k = m-1;
		}
		odp[i] -= t[p].lewo;
		odp[i-1] += t[p].prawo;
		odl -= t[p].prawo;
		odl += t[p].lewo;
		//cout << i << " " << odl << "\n";
		if(t[p].kogo_ruch == 1) odp[i] += odl;
		if(t[p].kogo_ruch == 2) odp[i-1] += odl; 
	}
	//rep(i,0,q) cout << i << " " << t[i].lewo << " " << t[i].prawo << " " << t[i].suma << " " << t[i].kogo_ruch << "\n";
	rep(i,1,n) cout << odp[i] << "\n";
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67