oj.uz

답안 #412983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412983 2021-05-27T22:53:49 Z Chaska Snowball (JOI21_ho_t2) C++11
100 / 100
 244 ms 16956 KB 
#include <bits/stdc++.h> 
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592
#define fo(i,n) for (int i=0;i<n;i++)
#define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) 
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N=2e5+5,mod=1e9+7;

ll n,q,a[N],w[N],acu,tam[N];
ll X[N],Y[N];
vector<pair<ll,ll>> group; // sortear por fi
ll res[N];

int main() { 
	cin.tie(0); cout.tie(0); 
	ios_base::sync_with_stdio();
	cin >> n >> q;
	fo(i,n) 
		cin >> a[i];
	fo(i,q) 
		cin >> w[i];
	ll x,y;
	x=y=0;
	fo(i,q) {
		acu += w[i];
		if (acu < x) x = acu;
		if (acu > y) y = acu;
		tam[i] = abs(x) + abs(y);
		
		X[i] = abs(x);
		Y[i] = abs(y);
  	}
	for (int i=0;i<n-1;i++) {
		ll p = a[i+1]-a[i];
		// tam del seg
		// do the bin ? 
		bool y = false;

				long long pp = 2e5;
				long long xd = -1;
				while (pp) { 	
					if (xd+pp<q && xd+pp >= 0 && tam[xd+pp]<p) {
						xd += pp;
					
					} else {
						pp /=2;
					}
				}

				int j = xd;
				
				j++;
				//cout << j << " ";
				if (j==0) {
					if (w[0]>=0)
						res[i] += p;
					else res[i+1] += p;
				} else {
				res[i] += Y[j-1];
				res[i+1] += X[j-1];
				p -= tam[j-1];
				if (j<q && w[j]>=0)
					res[i] += p;
				else 
					if (j<q) res[i+1] += p;
				}
		
		
	}
	res[0] += X[q-1];
	res[n-1] += Y[q-1];
	fo(i,n) cout << res[i] << "\n";
	return 0;
}
// Recuerda limites 
// Recuerda casos especiales

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:52:8: warning: unused variable 'y' [-Wunused-variable]
   52 |   bool y = false;
      |        ^

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 3 ms 332 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct

Subtask #2
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 3 ms 332 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 95 ms 6460 KB Output is correct
21 Correct 85 ms 6596 KB Output is correct
22 Correct 80 ms 6428 KB Output is correct
23 Correct 73 ms 6492 KB Output is correct
24 Correct 81 ms 7024 KB Output is correct
25 Correct 223 ms 11352 KB Output is correct
26 Correct 232 ms 14916 KB Output is correct
27 Correct 217 ms 14592 KB Output is correct
28 Correct 239 ms 14856 KB Output is correct
29 Correct 244 ms 14236 KB Output is correct
30 Correct 203 ms 13564 KB Output is correct
31 Correct 165 ms 13024 KB Output is correct
32 Correct 164 ms 13180 KB Output is correct
33 Correct 24 ms 1792 KB Output is correct
34 Correct 244 ms 15232 KB Output is correct
35 Correct 222 ms 14716 KB Output is correct
36 Correct 242 ms 14896 KB Output is correct
37 Correct 232 ms 14756 KB Output is correct
38 Correct 215 ms 14656 KB Output is correct
39 Correct 220 ms 14856 KB Output is correct
40 Correct 193 ms 14784 KB Output is correct
41 Correct 109 ms 9312 KB Output is correct
42 Correct 175 ms 13268 KB Output is correct
43 Correct 233 ms 16452 KB Output is correct
44 Correct 106 ms 9112 KB Output is correct
45 Correct 193 ms 14636 KB Output is correct
46 Correct 235 ms 16568 KB Output is correct
47 Correct 242 ms 16832 KB Output is correct
48 Correct 244 ms 16956 KB Output is correct