oj.uz

답안 #396213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396213 2021-04-29T14:39:51 Z Knps4422 Snowball (JOI21_ho_t2) C++14
0 / 100
 8 ms 460 KB 
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
typedef complex<int> point;
const int nmax = 400005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = 1e9;
const int sq = 5000;

int n, q;
ll pos[nmax], wind[nmax];
ll lef[nmax], rig[nmax];
ll cnt[nmax];

int main(){
	cin >> n >> q;
	for (int i = 0; i < n; ++i)
	{
		cin >> pos[i];
	}
	ll ps = 0;
	for (int i = 0; i < q; ++i)
	{
		cin >> wind[i];
		ps += wind[i];
		rig[i] = max(rig[i] , ps);
		//cout << rig[i] << ' ';
		rig[i+1] = rig[i];
		lef[i] = min(lef[i] , ps);
		//cout << lef[i] << '\n';
		lef[i+1] = lef[i];
	}
	cnt[0] -= lef[q-1];
	cnt[n-1] += rig[q-1];
	for(int i = 0; i < n; i++){
		ll l = pos[i] , r = pos[i+1];
		if(l + rig[q-1] - lef[q-1] >= r){
		while(l < r){
			ll mid = (r-l)/2 + l;
			int lt = 0, rt = q-1;
			while(lt < rt){
				int md = (lt+rt)/2;
				if(pos[i] + rig[md] - 1 >= mid){
					rt = md;
				}else{
					lt = md+1;
				}
			}
			int t1 = lt;
			if(mid == pos[i])t1 = -1;
			lt = 0, rt = q-1;
			while(lt < rt){
				int md = (lt+rt)/2;
				if(pos[i+1] + lef[md] <= mid){
					rt = md;
				}else{
					lt = md+1;
				}
			}
			int t2 = lt;
			if(mid == pos[i+1])t2 = -1;
			if(t1 <= t2){
				l = mid+1;
			}else{
				r = mid;
			}
		}
		//cout << i << ' ' << pos[i] << ' ' << l << ' ' << pos[i+1]<< '\n';
		cnt[i] += l - pos[i];
		cnt[i+1] += pos[i+1] - l;
		}else{
			cnt[i] += rig[q-1];
			cnt[i+1] -= lef[q-1];
		}
		//cout << "CH " << i << '\n';
	}
	ll sm = 0;
	for(int i = 0; i < n; i++){
		cout << cnt[i] << '\n';
		sm += cnt[i];
	}

}

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 8 ms 360 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Incorrect 7 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 8 ms 360 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Incorrect 7 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -