oj.uz

Submission #422043

# Submission time Handle Problem Language Result Execution time Memory
422043 2021-06-09T15:50:39 Z amunduzbaev Snowball (JOI21_ho_t2) C++14
33 / 100
 2500 ms 1992 KB 
/* made by amunduzbaev */
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"
 
using namespace std;
//~ using namespace __gnu_pbds;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
#define int long long
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update> ordered_set;
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int qq[N];

pii rng(int i, int r){
	int x = a[i];
	int l = x, rx = x;
	for(int i=0;i<=r;i++){
		x += qq[i];
		umin(l, x), umax(rx, x);
	} return mp(l, rx);
}

void solve(int t_case){
	cin>>n>>q;
	a[0] = -inf, a[n+1] = inf;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<q;i++) cin>>qq[i];
	for(int i=1;i<=n;i++){
		int l = 0, r = q-1;
		int L, R;
		if(rng(i-1, r).ss >= rng(i, r).ff){
			while(l < r){
				int m = (l + r)>>1;
				pii mx = rng(i, m), lx = rng(i - 1, m);
				if(lx.ss >= mx.ff) r = m;
				else l = m + 1;
			} pii lx = rng(i-1, l), m = rng(i, l);
			if(qq[l] > 0) L = m.ff;
			else L = lx.ss;
		} else L = rng(i, r).ff;
		
		l = 0, r = q-1;
		if(rng(i, r).ss >= rng(i+1, r).ff){
			while(l < r){
				int m = (l + r)>>1;
				pii mx = rng(i, m), rx = rng(i + 1, m);
				if(mx.ss >= rx.ff) r = m;
				else l = m + 1;
			} pii m = rng(i, l), rx = rng(i+1, l);
			if(qq[l] < 0) R = m.ss;
			else R = rx.ff;
		} else R = rng(i, r).ss;
		
		cout<<R - L<<"\n";
	}
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

Main.cpp: In function 'void usaco(std::string)':
Main.cpp:32:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 13 ms 344 KB Output is correct
4 Correct 150 ms 348 KB Output is correct
5 Correct 128 ms 352 KB Output is correct
6 Correct 126 ms 348 KB Output is correct
7 Correct 129 ms 344 KB Output is correct
8 Correct 126 ms 336 KB Output is correct
9 Correct 123 ms 336 KB Output is correct
10 Correct 135 ms 336 KB Output is correct
11 Correct 149 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 128 ms 360 KB Output is correct
16 Correct 132 ms 332 KB Output is correct
17 Correct 103 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 29 ms 332 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 13 ms 344 KB Output is correct
4 Correct 150 ms 348 KB Output is correct
5 Correct 128 ms 352 KB Output is correct
6 Correct 126 ms 348 KB Output is correct
7 Correct 129 ms 344 KB Output is correct
8 Correct 126 ms 336 KB Output is correct
9 Correct 123 ms 336 KB Output is correct
10 Correct 135 ms 336 KB Output is correct
11 Correct 149 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 128 ms 360 KB Output is correct
16 Correct 132 ms 332 KB Output is correct
17 Correct 103 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 29 ms 332 KB Output is correct
20 Correct 46 ms 1848 KB Output is correct
21 Correct 223 ms 1868 KB Output is correct
22 Correct 1855 ms 1992 KB Output is correct
23 Execution timed out 2571 ms 1880 KB Time limit exceeded
24 Halted 0 ms 0 KB -