oj.uz

Submission #916956

# Submission time Handle Problem Language Result Execution time Memory
916956 2024-01-26T20:37:35 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long


struct node
{
	int left, right;
	int sum, lazy;
	int l, r;
	int maxi;
	node() {
		sum=0, left=-1, right=-1, maxi=0;
	}
};

node st[123456*64];
int cnt=1;
multiset<int> act;

void update(int root, int left, int right, int qLeft, int qRight, int nValue)
{
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight) {
		st[root].sum+=left*nValue;
		if (st[root].sum!=0) st[root].maxi=left;
		else st[root].maxi=0;
		return;
	}
	int mid=(left+right)/2;
	if (st[root].left==-1) {
		st[root].left = cnt++;
		st[ st[root].left ].l=left, st[ st[root].left ].r=mid;
	}
	if (st[root].right==-1) {
		st[root].right = cnt++;
		st[ st[root].right ].l=mid+1, st[ st[root].right ].r=right;
	}
	if (mid>=qLeft) update(st[root].left, left, mid, qLeft, qRight, nValue);
	if (mid+1<=qRight) update(st[root].right, mid+1, right, qLeft, qRight, nValue);
	st[root].sum=st[ st[root].left ].sum + st[ st[root].right ].sum;
	st[root].maxi=st[ st[root].right ].maxi - st[ st[root].left ].sum;
	st[root].maxi=max(st[ st[root].left ].maxi, st[root].maxi);
	st[root].maxi=max(st[root].maxi, 0LL);
	return;
}

int mx;

bool init(signed n, long long mxx, long long coins[]) {
	mx=mxx+100;
	st[0].l=1, st[0].r=mx+1;
	for (int i=0; i<n; i++) update(0, 1, mx+1, coins[i], coins[i], 1), act.insert(coins[i]);
	//update(0, 1, mx+1, *act.begin(), *act.begin(), -1);
	int ans=st[0].maxi;
	//update(0, 1, mx+1, *act.begin(), *act.begin(), 1);
	return ans<=1;
}
bool is_happy(signed event, signed n, long long coins[]) {
	for (int i=0; i<n; i++) {
		update(0, 1, mx+1, coins[i], coins[i], event);
		if (event==1) act.insert(coins[i]);
		else act.erase(act.find(coins[i]));
	}
	//update(0, 1, mx+1, *act.begin(), *act.begin(), -1);
	int ans=st[0].maxi;
	//update(0, 1, mx+1, *act.begin(), *act.begin(), 1);
	return ans<=1;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 433232 KB Output is correct
2 Correct 120 ms 433232 KB Output is correct
3 Correct 114 ms 433280 KB Output is correct
4 Correct 123 ms 433236 KB Output is correct
5 Correct 97 ms 433192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 433232 KB Output is correct
2 Correct 120 ms 433232 KB Output is correct
3 Correct 114 ms 433280 KB Output is correct
4 Correct 123 ms 433236 KB Output is correct
5 Correct 97 ms 433192 KB Output is correct
6 Correct 97 ms 433232 KB Output is correct
7 Correct 96 ms 433336 KB Output is correct
8 Correct 114 ms 434000 KB Output is correct
9 Correct 120 ms 434064 KB Output is correct
10 Correct 108 ms 434000 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 433232 KB Output is correct
2 Correct 120 ms 433232 KB Output is correct
3 Correct 114 ms 433280 KB Output is correct
4 Correct 123 ms 433236 KB Output is correct
5 Correct 97 ms 433192 KB Output is correct
6 Correct 487 ms 442300 KB Output is correct
7 Correct 485 ms 441900 KB Output is correct
8 Correct 504 ms 442044 KB Output is correct
9 Correct 822 ms 443712 KB Output is correct
10 Correct 1039 ms 445916 KB Output is correct
11 Correct 341 ms 446424 KB Output is correct
12 Correct 336 ms 446548 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 433232 KB Output is correct
2 Correct 120 ms 433232 KB Output is correct
3 Correct 114 ms 433280 KB Output is correct
4 Correct 123 ms 433236 KB Output is correct
5 Correct 97 ms 433192 KB Output is correct
6 Correct 97 ms 433232 KB Output is correct
7 Correct 96 ms 433336 KB Output is correct
8 Correct 114 ms 434000 KB Output is correct
9 Correct 120 ms 434064 KB Output is correct
10 Correct 108 ms 434000 KB Output is correct
11 Correct 487 ms 442300 KB Output is correct
12 Correct 485 ms 441900 KB Output is correct
13 Correct 504 ms 442044 KB Output is correct
14 Correct 822 ms 443712 KB Output is correct
15 Correct 1039 ms 445916 KB Output is correct
16 Correct 341 ms 446424 KB Output is correct
17 Correct 336 ms 446548 KB Output is correct
18 Execution timed out 3206 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -