oj.uz

답안 #260020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260020 2020-08-09T00:34:26 Z mjkocijan Two Dishes (JOI19_dishes) C++14
0 / 100
 502 ms 61896 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
#define X first
#define Y second
#define pb push_back
typedef long double ld;
#define MAXN 1001001

int n, m, nn = 1 << 20;
ll a[MAXN], s[MAXN], p[MAXN];
ll b[MAXN], u[MAXN], k[MAXN];
vector<ii> x[MAXN];
ll ap[MAXN], bp[MAXN];
ll t[4 * MAXN];
ll pd[4 * MAXN], pm[4 * MAXN];

void propaj(int cv)
{
	t[cv] += pd[cv];
	t[cv] = max(t[cv], pm[cv]);
	pd[cv * 2] += pd[cv];
	pd[cv * 2 + 1] += pd[cv];
	pm[cv * 2] += pm[cv];
	pm[cv * 2 + 1] += pm[cv];
	pd[cv] = pm[cv] = 0;
}

void dodaj(int cv, int lo, int hi, int l, int r, ll h)
{
	propaj(cv);

  if (lo > hi || lo > r || hi < r || l > r) return;
  
  if (lo >= l && hi <= r) {
  	pd[cv] += h;
  	pm[cv] += h;
  	return;
  }
  
  int mid = (lo + hi) / 2;
  
  dodaj(cv * 2, lo, mid, l, r, h);
  dodaj(cv * 2 + 1, mid + 1, hi, l, r, h);
}

void maxaj(int cv, int lo, int hi, int l, int r, ll h)
{
	propaj(cv);

  if (lo > hi || lo > r || hi < r || l > r) return;
  
  if (lo >= l && hi <= r) {
  	pm[cv] = max(pm[cv], h);
  	return;
  }
  
  int mid = (lo + hi) / 2;
  
  maxaj(cv * 2, lo, mid, l, r, h);
  maxaj(cv * 2 + 1, mid + 1, hi, l, r, h);
}

ll kveri(int cv, int lo, int hi, int h)
{
	propaj(cv);
	
	if (lo == hi) {
		return t[cv];
	}
	
	int mid = (lo + hi) / 2;
	
	if (h <= mid)
		return kveri(cv * 2, lo, mid, h);
	else
		return kveri(cv * 2 + 1, mid + 1, hi, h);
}

ll reza = 0LL;

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
  	scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
  	ap[i + 1] = a[i] + (i ? a[i - 1] : 0);
  }
  for (int i = 0; i < m; i++) {
  	scanf("%lld%lld%lld", &b[i], &u[i], &k[i]);
  	bp[i + 1] = b[i] + (i ? b[i - 1] : 0);
  }
  for (int i = 0; i < n; i++) {
  	x[i].pb({upper_bound(bp, bp + m + 1, (s[i] - ap[i + 1])) - bp, p[i]});
  }
  for (int i = 0; i < m; i++) {
  	ll izraz = upper_bound(ap, ap + n + 1, (u[i] - bp[i + 1])) - ap - 1;
  	if (izraz)
  		x[izraz].pb({i + 1, -k[i]});
  	reza += k[i];
  }
  for (int i = 0; i <= n; i++) {
  	for (ii j: x[i]) {
  		//cout << i << ' ' << j.X << ' ' << j.Y << endl;
  		dodaj(1, 0, nn - 1, 0, j.X - 1, j.Y);
  	}
  	for (ii j: x[i]) {
  		if (j.X)
  			maxaj(1, 0, nn - 1, j.X, m, kveri(1, 0, nn - 1, j.X - 1));
  	}
  }
  printf("%lld\n", reza + kveri(1, 0, nn - 1, m));
  return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld", &b[i], &u[i], &k[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

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

Subtask #8
0 / 9.0

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