oj.uz

Submission #421737

# Submission time Handle Problem Language Result Execution time Memory
421737 2021-06-09T11:30:03 Z Kerim Snowball (JOI21_ho_t2) C++17
33 / 100
 2500 ms 1984 KB 
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll arr[MAXN],w[MAXN];
PII rng[3];
const ll I=1e16;
bool intersect(PII a, PII b){
	if(a.ff>b.ff)swap(a,b);
	return (b.ff<=a.ss and a.ss<=b.ss);
}
PII get(int pos,int ind){
	PII tmp={arr[pos],arr[pos]};
	ll cur=arr[pos];
	for(int i=1;i<=ind;i++){
		cur+=w[i];
		umin(tmp.ff,cur);
		umax(tmp.ss,cur);
	}
	return tmp;
}
int main(){
    //freopen("file.in", "r", stdin);
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
		scanf("%lld",arr+i);
	arr[0]=-I;
	arr[n+1]=I;
	for(int i=1;i<=q;i++)
		scanf("%lld",w+i);
	for(int i=1;i<=n;i++){
		ll A=get(i,q).ff,B=get(i,q).ss;
		if(intersect(get(i-1,q), get(i,q))){
			int st=1,en=q;
			while(st+1<en){
				int mid=(st+en)>>1;
				if(intersect(get(i-1,mid), get(i,mid)))en=mid;
				else st=mid;
			}
			if(intersect(get(i-1,st), get(i,st)))en=st;
			if(w[en]<0)A=get(i-1,en).ss;
			else A=get(i,en).ff;
		}
		if(intersect(get(i+1,q),get(i,q))){
			int st=1,en=q;
			while(st+1<en){
				int mid=(st+en)>>1;
				if(intersect(get(i+1,mid),get(i,mid)))en=mid;
				else st=mid;
			}
			if(intersect(get(i+1,st),get(i,st)))en=st;
			if(w[en]<0)B=get(i,en).ss;
			else B=get(i+1,en).ff;
		}
		printf("%lld\n",B-A);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%lld",arr+i);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%lld",w+i);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 16 ms 320 KB Output is correct
4 Correct 156 ms 460 KB Output is correct
5 Correct 149 ms 328 KB Output is correct
6 Correct 152 ms 324 KB Output is correct
7 Correct 153 ms 332 KB Output is correct
8 Correct 151 ms 332 KB Output is correct
9 Correct 151 ms 332 KB Output is correct
10 Correct 152 ms 204 KB Output is correct
11 Correct 154 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 151 ms 456 KB Output is correct
16 Correct 151 ms 324 KB Output is correct
17 Correct 121 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 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 16 ms 320 KB Output is correct
4 Correct 156 ms 460 KB Output is correct
5 Correct 149 ms 328 KB Output is correct
6 Correct 152 ms 324 KB Output is correct
7 Correct 153 ms 332 KB Output is correct
8 Correct 151 ms 332 KB Output is correct
9 Correct 151 ms 332 KB Output is correct
10 Correct 152 ms 204 KB Output is correct
11 Correct 154 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 151 ms 456 KB Output is correct
16 Correct 151 ms 324 KB Output is correct
17 Correct 121 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 48 ms 1760 KB Output is correct
21 Correct 258 ms 1976 KB Output is correct
22 Correct 2062 ms 1976 KB Output is correct
23 Execution timed out 2568 ms 1984 KB Time limit exceeded
24 Halted 0 ms 0 KB -