Submission #260019

#	Time	Username	Problem	Language	Result	Execution time	Memory
260019		mjkocijan	Two Dishes (JOI19_dishes)	C++14	0 / 100	367 ms	53636 KiB

dishes

#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];
/*queue<ii> q[4 * MAXN];

void propaj(int cv)
{
	while (!q[cv].empty()) {
		ii cu = q[cv].front();
		q[cv].pop();
		
		if (cu.X) {
			t[cv] += cu.Y;
			if (cv < nn) {
				q[cv * 2].push(cu);
				q[cv * 2 + 1].push(cu);
			}
		} else {
			t[cv] = max(t[cv], cu.Y);
			if (cv < nn) {
				q[cv * 2].push(cu);
				q[cv * 2 + 1].push(cu);
			}
		}
	}
}*/

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) {
  	//q[cv].push({1, 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) {
  	//q[cv].push({0, 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 (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:95: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:97: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:101: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
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9