제출 #1291402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291402		trinm01	Snowball (JOI21_ho_t2)	C++20	33 / 100	2164 ms	73508 KiB

Main

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll oo = 1e18 + 7;  
const int base = 10;

int n, q;
ll a[MAXN];
ll k[MAXN];
ll ps[MAXN];

ll stmi[MAXN][20], stmx[MAXN][20], lg[MAXN];
void build(){
	FOR(i, 1, q){
		stmi[i][0]=ps[i];
		stmx[i][0]=ps[i];
		lg[i]=__lg(i);
	}
	FOR(j, 1, 19){
		for(int i=1; i+(1<<j)-1<=q; i++){
			stmi[i][j]=min(stmi[i][j-1], stmi[i+(1<<(j-1))][j-1]);
			stmx[i][j]=max(stmx[i][j-1], stmx[i+(1<<(j-1))][j-1]);
		}
	}
}
ll getmi(int l, int r){
	int k=lg[r-l+1];
	return min(stmi[l][k], stmi[r-(1<<k)+1][k]);
}
ll getmx(int l, int r){
	int k=lg[r-l+1];
	return max(stmx[l][k], stmx[r-(1<<k)+1][k]);
}

int find1(ll s, ll t){
	int l=1, r=q, pos=1e9;
	while(l<=r){
		int mid=(l+r)/2;
		if(s+getmi(1, mid)<=t){
			pos=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return pos;
}
int find2(ll s, ll t){
	int l=1, r=q, pos=1e9;
	while(l<=r){
		int mid=(l+r)/2;
		if(s+getmx(1, mid)>=t){
			pos=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return pos;
}

ll res[MAXN];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    // freopen("test.txt", "r", stdin);
    // freopen("o2.out", "w", stdout);

    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> n >> q;
    FOR(i, 1, n){
    	cin >> a[i];
    }
    FOR(i, 1, q){
    	cin >> k[i];
    }
    FOR(i, 1, q){
    	ps[i]=ps[i-1]+k[i];
    }
    
    build();
    
    a[0]=-oo;
    a[n+1]=oo;
    FOR(i, 1, n){
    	ll l=max(a[i-1], a[i]+getmi(1, q)), r=a[i], pos=a[i];
    	// cout << l << ' ' << r << '\n';
    	while(l<=r){
    		ll mid=(l+r)/2;
    		if(find2(a[i-1], mid+1)>find1(a[i], mid)){
    			pos=mid;
    			r=mid-1;
    		}
    		else{
    			l=mid+1;
    		}
    	}
    	res[i]+=(a[i]-pos);
    	res[i-1]+=(min(a[i-1]+getmx(1, q), pos)-a[i-1]);
    }
    res[n]+=(a[n]+getmx(1, q)-a[n]);
    FOR(i, 1, n){
    	cout << res[i] << '\n';
    }
    
    return 0;
}

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

Main.cpp: In function 'int main()':
Main.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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