oj.uz

Submission #588790

# Submission time Handle Problem Language Result Execution time Memory
588790 2022-07-04T04:57:41 Z Red_Inside Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 36332 KB 
//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+10,LOG=17, mod=1e9+7;
int block = 320, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
#define int ll
const ll inf=1e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int q, l, ty[maxn], x[maxn], a[maxn], n, sug[maxn], ants[maxn];
vector <int> vec;
map <int, int> mapp;

main()
{
	IOS
	cin >> q >> l;
	forn(1, i, q)
	{
		cin >> ty[i] >> x[i] >> a[i];
		vec.pb(x[i]);
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	n = vec.size();
	FOR(0, i, n)
	{
		mapp[vec[i]] = i;
	}
	forn(1, i, q)
	{
		x[i] = mapp[x[i]];
	}
	forn(1, iter, q)
	{
//		cout << "Add " << x[iter] << " " << a[iter] << endl;
		if(ty[iter] == 1)
		{
			ants[x[iter]] += a[iter];
		}
		else
		{
			sug[x[iter]] += a[iter];
		}
		stack <pii> stac;
		nfor(0, i, n-1)
		{
			if(sug[i]) stac.push({sug[i], i});
		}
		int ans = 0;
		forn(0, i, n-1)
		{
			while(stac.size() && stac.top().s < i && vec[i] - vec[stac.top().s] > l)
			{
				stac.pop();
			}
			int temp = ants[i];
			while(temp && stac.size() && abs(vec[i] - vec[stac.top().s]) <= l)
			{
				if(stac.top().f < temp)
				{
					temp -= stac.top().f;
					ans += stac.top().f;
					stac.pop();
				}
				else
				{
					stac.top().f -= temp;
					ans += temp;
					temp = 0;
				}
			}
		}
		cout << ans << "\n";
	}
}

Compilation message

sugar.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main()
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 39 ms 596 KB Output is correct
7 Correct 28 ms 580 KB Output is correct
8 Correct 11 ms 492 KB Output is correct
9 Correct 10 ms 468 KB Output is correct
10 Correct 93 ms 780 KB Output is correct
11 Correct 102 ms 780 KB Output is correct
12 Correct 113 ms 860 KB Output is correct
13 Correct 105 ms 924 KB Output is correct
14 Correct 111 ms 748 KB Output is correct
15 Correct 126 ms 804 KB Output is correct
16 Correct 65 ms 776 KB Output is correct
17 Correct 59 ms 724 KB Output is correct
18 Correct 46 ms 740 KB Output is correct
19 Correct 96 ms 800 KB Output is correct
20 Correct 46 ms 724 KB Output is correct
21 Correct 98 ms 808 KB Output is correct
22 Correct 47 ms 724 KB Output is correct
23 Correct 79 ms 784 KB Output is correct
24 Correct 46 ms 732 KB Output is correct
25 Correct 75 ms 724 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Execution timed out 4025 ms 36332 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 4038 ms 25564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 39 ms 596 KB Output is correct
7 Correct 28 ms 580 KB Output is correct
8 Correct 11 ms 492 KB Output is correct
9 Correct 10 ms 468 KB Output is correct
10 Correct 93 ms 780 KB Output is correct
11 Correct 102 ms 780 KB Output is correct
12 Correct 113 ms 860 KB Output is correct
13 Correct 105 ms 924 KB Output is correct
14 Correct 111 ms 748 KB Output is correct
15 Correct 126 ms 804 KB Output is correct
16 Correct 65 ms 776 KB Output is correct
17 Correct 59 ms 724 KB Output is correct
18 Correct 46 ms 740 KB Output is correct
19 Correct 96 ms 800 KB Output is correct
20 Correct 46 ms 724 KB Output is correct
21 Correct 98 ms 808 KB Output is correct
22 Correct 47 ms 724 KB Output is correct
23 Correct 79 ms 784 KB Output is correct
24 Correct 46 ms 732 KB Output is correct
25 Correct 75 ms 724 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Execution timed out 4025 ms 36332 KB Time limit exceeded
30 Halted 0 ms 0 KB -