oj.uz

Submission #960060

# Submission time Handle Problem Language Result Execution time Memory
960060 2024-04-09T15:14:23 Z aaron_dcoder Food Court (JOI21_foodcourt) C++17
21 / 100
 493 ms 22452 KB 
#define NDEBUG

#ifdef NDEBUG

#define dbg(TXT) (void)0;
#define dbgv(VAR) (void)0;
#define dbgfor if constexpr (false) for

#else

#define _GLIBCXX_DEBUG
#define dbg(TXT) cerr << TXT << "\n";
#define dbgv(VAR) cerr << #VAR << " = " << VAR <<", line "<< __LINE__ << '\n';
#define dbgfor for

#endif

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll,ll>;
#define e0 first
#define e1 second

constexpr ll INFTY = 2e18;

struct segtree
{
	vector<ll> toadd;
	vector<ll> currfloor;

	segtree(ll n)
	{
		toadd.assign(4*n,0);
		currfloor.assign(4*n,0);
	}

	void add(ll val, ll base, ll baseforced, ll lseg, ll rseg, ll l, ll r, ll node)
	{
		currfloor[node] = max(currfloor[node],baseforced);
		if (rseg<l || r<lseg) return;

		if (lseg<=l && r<=rseg)
		{
			toadd[node]+=val;
			currfloor[node] = max(currfloor[node],base);
			currfloor[node]+=val;
			return;
		}


		ll mid = (l+r)/2;
		add(val, base-toadd[node], currfloor[node]-toadd[node], lseg, rseg, l,mid,node*2);
		add(val, base-toadd[node], currfloor[node]-toadd[node], lseg, rseg, mid+1,r,node*2+1);
		currfloor[node]=-INFTY;
	}

	ll get(ll x, ll l, ll r, ll node)
	{
		if (x<l || r<x) return 0;

		if (l==r)
		{
			//if (node==11)dbgv(currfloor[node]);
			return currfloor[node];
		}

		ll mid = (l+r)/2;
		ll o =max(toadd[node]+(get(x, l,mid,node*2)+get(x, mid+1,r,node*2+1)),currfloor[node]);
		if (o<0 && node==5){
		//	dbgv(mid+1 << r);
		//	dbgv(get(x, mid+1,r,node*2+1));
		}
		return o;
	}
};

int main()
{
	ll N,M,Q;
	cin >> N >> M >> Q;

	//if (M!=1) throw exception();

	segtree stree(N);
		dbgfor (ll i=1;i<=N;i++)
		{
			cerr << stree.get(i, 1,N,1) << " ";
		}
		dbg("");

	for (ll qno = 0; qno < Q; ++qno)
	{
		ll t;
		cin >> t;

		if (t==1)
		{
			ll l,r,c,k;
			cin >> l >> r >> c >> k;
			stree.add(k,0,-INFTY,l,r, 1,N,1);
		}
		else if (t==2)
		{
			ll l,r,k;
			cin >> l >> r >> k;
			stree.add(-k,k,-INFTY,l,r, 1,N,1);
		}
		else
		{
			assert(t==3);
			ll a,b;
			cin >> a >> b;
			if (b<=stree.get(a, 1,N,1))
			{
				cout << "1\n";
			}
			else cout << "0\n";
		}
		dbgv(qno);
		dbgfor (ll i=1;i<=N;i++)
		{
			cerr << stree.get(i, 1,N,1) << " ";
		}dbg("");


		dbgfor (ll i:stree.toadd)
		{
		//	cerr << i << " ";
		}dbg("");
		dbgfor (ll i:stree.currfloor)
		{
		//	cerr << i << " ";
		}dbg("");
	}
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:128:14: warning: unused variable 'i' [-Wunused-variable]
  128 |   dbgfor (ll i:stree.toadd)
      |              ^
foodcourt.cpp:132:14: warning: unused variable 'i' [-Wunused-variable]
  132 |   dbgfor (ll i:stree.currfloor)
      |              ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 5512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 14500 KB Output is correct
2 Correct 294 ms 16928 KB Output is correct
3 Correct 391 ms 22096 KB Output is correct
4 Correct 300 ms 20300 KB Output is correct
5 Correct 281 ms 16716 KB Output is correct
6 Correct 385 ms 22340 KB Output is correct
7 Correct 243 ms 4692 KB Output is correct
8 Correct 255 ms 4432 KB Output is correct
9 Correct 444 ms 22312 KB Output is correct
10 Correct 493 ms 22412 KB Output is correct
11 Correct 384 ms 22320 KB Output is correct
12 Correct 378 ms 22100 KB Output is correct
13 Correct 383 ms 22080 KB Output is correct
14 Correct 383 ms 22236 KB Output is correct
15 Correct 385 ms 22452 KB Output is correct
16 Correct 377 ms 22104 KB Output is correct
17 Correct 396 ms 22188 KB Output is correct
18 Correct 383 ms 22100 KB Output is correct
19 Correct 405 ms 22100 KB Output is correct
20 Correct 370 ms 22216 KB Output is correct
21 Correct 381 ms 21984 KB Output is correct
22 Correct 385 ms 21984 KB Output is correct
23 Correct 397 ms 22444 KB Output is correct
24 Correct 396 ms 22048 KB Output is correct
25 Correct 369 ms 18012 KB Output is correct
26 Correct 387 ms 21840 KB Output is correct
27 Correct 317 ms 21840 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 5764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -