Submission #260183

#	Time	Username	Problem	Language	Result	Execution time	Memory
260183		mjkocijan	Two Dishes (JOI19_dishes)	C++14	100 / 100	7409 ms	218744 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
#define INF 1001001001001001001LL

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)
{
	//if (cv >= nn) cout << " (" << cv - nn << ' ' << t[cv] << ' '<< pd[cv] << ' ' << (pm[cv] < -INF / 2 ? -9 : pm[cv])<<") ";
	t[cv] += pd[cv];
	t[cv] = max(t[cv], pm[cv]);
	if (cv < nn) {
		pd[cv * 2] += pd[cv];
		pd[cv * 2 + 1] += pd[cv];
		pm[cv * 2] += pd[cv];
		pm[cv * 2 + 1] += pd[cv];
		pm[cv * 2] = max(pm[cv * 2], pm[cv]);
		pm[cv * 2 + 1] = max(pm[cv * 2 + 1], pm[cv]);
	}
	pd[cv] = 0;
	pm[cv] = -INF;
}

void dodaj(int cv, int lo, int hi, int l, int r, ll h)
{
	propaj(cv);//cout<<cv<<' '<<lo<<' '<<hi<<' '<<l<<' '<<r<<' '<<h<<endl;

  if (lo > hi || lo > r || hi < l || l > r) return;//cout<<"ok!\n";
  
  if (lo >= l && hi <= r) {//cout<<'.'<<lo<<'.'<<hi<<'.'<<h<<endl;
  	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 < l || 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, r[MAXN], r2[MAXN];

int main()
{
	for (int i = 0; i < 4 * MAXN; i++)
		pm[i] = -INF;
  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 ? ap[i] : 0);
  }
  for (int i = 0; i < m; i++) {
  	scanf("%lld%lld%lld", &b[i], &u[i], &k[i]);
  	bp[i + 1] = b[i] + (i ? bp[i] : 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 == n)
  		reza += k[i];
  	else if (izraz >= 0) {
  		x[izraz].pb({i + 1, -k[i]});
  	reza += k[i];//cout<<izraz<<".,..";
  	//r2[i + 1] += k[i];
  	}
  }
  //for (int i = 0; i <= m; i++) r[i] = r2[i] + (i ? r[i - 1] : 0);
  for (int i = 0; i <= n; i++) {
  	//cout << i << ": ";
  	for (ii j: x[i]) {
  		//cout << j.X <<' '<<j.Y<<", ";
  		dodaj(1, 0, nn - 1, 0, j.X - 1, j.Y);//for (int j = 0; j <= m; j++) cout << kveri(1, 0, nn - 1, j) << ' '; cout << endl;
  	}//cout << endl;
  	for (ii j: x[i]) {
  		//if (j.X)
  			maxaj(1, 0, nn - 1, j.X, m, kveri(1, 0, nn - 1, j.X - 1));//for (int j = 0; j <= m; j++) cout << kveri(1, 0, nn - 1, j) << ' '; cout << endl;
  	}
  	//for (int j = 0; j <= m; j++) cout << kveri(1, 0, nn - 1, j) << ' '; cout << endl;
  }//cout<<reza<<endl;
  printf("%lld\n", reza + kveri(1, 0, nn - 1, m));
  return 0;
}

Compilation message (stderr)

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