oj.uz

답안 #554017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554017 2022-04-27T14:46:27 Z MilosMilutinovic Two Antennas (JOI19_antennas) C++14
22 / 100
 434 ms 43616 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=200050;
const ll inf=(ll)1e18;
int n,q,h[N],a[N],b[N],ql[N],qr[N];
ll ans[N];
vector<PII> Qs[N][2];

struct node{
	ll val,mx,lzy;
}nd[8*N];
void upd(int p,ll x) {
	nd[p].val=max(nd[p].val,nd[p].mx+x);
	nd[p].lzy=max(nd[p].lzy,x);
}
void push(int p) {
	if (nd[p].lzy==-inf) return;
	upd(p*2,nd[p].lzy);
	upd(p*2+1,nd[p].lzy);
	nd[p].lzy=-inf;
}
void build(int p,int l,int r) {
	nd[p].val=nd[p].mx=nd[p].lzy=-inf;
	if (l==r) return;
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void modify(int p,int l,int r,int tl,ll x) {
	if (l==r) {
		nd[p].mx=x;
		return;
	}
	push(p);
	int mid=(l+r)/2;
	if (tl<=mid) modify(p*2,l,mid,tl,x);
	else modify(p*2+1,mid+1,r,tl,x);
	nd[p].mx=max(nd[p*2].mx,nd[p*2+1].mx);
}
void update(int p,int l,int r,int tl,int tr,ll x) {
	if (tl>tr||l>r||l>tr||r<tl) return;
	if (tl<=l&&r<=tr) {
		upd(p,x);
		push(p);
		return;
	}
	push(p);
	int mid=(l+r)/2;
	update(p*2,l,mid,tl,tr,x);
	update(p*2+1,mid+1,r,tl,tr,x);
	nd[p].val=max(nd[p*2].val,nd[p*2+1].val);
}
ll query(int p,int l,int r,int tl,int tr) {
	if (tl>tr||l>r||l>tr||r<tl) return -inf;
	if (tl<=l&&r<=tr) return nd[p].val;
	int mid=(l+r)/2;
	return max(query(p*2,l,mid,tl,tr),query(p*2+1,mid+1,r,tl,tr));
}

void solve() {
	rep(i,1,n+1) {
		Qs[i][0].clear();
		Qs[i][1].clear();
	}
	rep(i,1,n+1) {
		Qs[min(n+1,i+a[i])][0].pb(mp(i,0));
		Qs[min(n+1,i+b[i])][0].pb(mp(i,1));
	}
	rep(i,1,q+1) Qs[qr[i]][1].pb(mp(i,ql[i]));
	build(1,1,n);
	rep(i,1,n+1) {
		for (auto qs:Qs[i][0]) if (qs.se==0) modify(1,1,n,qs.fi,h[qs.fi]);
		update(1,1,n,i-b[i],i-a[i],-h[i]);
		for (auto qs:Qs[i][1]) ans[qs.fi]=max(ans[qs.fi],query(1,1,n,qs.se,i));
		for (auto qs:Qs[i][0]) if (qs.se==1) modify(1,1,n,qs.fi,-inf);
	}
}

int main() {
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d%d%d",&h[i],&a[i],&b[i]);
	scanf("%d",&q);
	rep(i,1,q+1) scanf("%d%d",&ql[i],&qr[i]),ans[i]=-1;
	solve();
	rep(i,1,n+1) h[i]=-h[i];
	solve();
	rep(i,1,q+1) printf("%lld\n",ans[i]);
	return 0;
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
antennas.cpp:101:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  rep(i,1,n+1) scanf("%d%d%d",&h[i],&a[i],&b[i]);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
antennas.cpp:103:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  rep(i,1,q+1) scanf("%d%d",&ql[i],&qr[i]),ans[i]=-1;
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 42840 KB Output is correct
2 Correct 375 ms 43448 KB Output is correct
3 Correct 246 ms 39196 KB Output is correct
4 Correct 390 ms 43440 KB Output is correct
5 Correct 151 ms 26432 KB Output is correct
6 Correct 386 ms 43448 KB Output is correct
7 Correct 349 ms 42424 KB Output is correct
8 Correct 409 ms 43572 KB Output is correct
9 Correct 48 ms 14820 KB Output is correct
10 Correct 434 ms 43576 KB Output is correct
11 Correct 239 ms 29496 KB Output is correct
12 Correct 418 ms 43616 KB Output is correct
13 Correct 262 ms 35948 KB Output is correct
14 Correct 228 ms 35440 KB Output is correct
15 Correct 233 ms 33284 KB Output is correct
16 Correct 186 ms 32672 KB Output is correct
17 Correct 288 ms 37260 KB Output is correct
18 Correct 236 ms 34388 KB Output is correct
19 Correct 252 ms 34336 KB Output is correct
20 Correct 256 ms 35496 KB Output is correct
21 Correct 246 ms 35948 KB Output is correct
22 Correct 249 ms 35688 KB Output is correct
23 Correct 243 ms 35396 KB Output is correct
24 Correct 189 ms 32388 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -