oj.uz

Submission #922276

# Submission time Handle Problem Language Result Execution time Memory
922276 2024-02-05T11:01:05 Z pan Fountain (eJOI20_fountain) C++17
100 / 100
 373 ms 46932 KB 
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;

ll n, q, tem, a, b;
ll const INF = 1e12;
ll twok[100005][25], summ[100005][25];
pi fountain[100005];
void init2k()
{
	for (ll k=1; k<=20; k++) for (ll x=1; x<=n; x++){twok[x][k] = n+1, summ[x][k] = INF;}
	for (ll k=1; k<=20; k++)
	{
		for (ll x=1; x<=n; x++)
		{
			if (twok[x][k-1]==n+1) continue;
			twok[x][k] = twok[twok[x][k-1]][k-1];
			summ[x][k] = summ[x][k-1] + summ[twok[x][k-1]][k-1];
		}
	}
}
int main()
{
	input(n); input(q);
	deque<pi> que;
	for (ll i=1; i<=n; ++i)
	{
		input(a); input(b);
		fountain[i] = mp(a,b);
		while (que.size() && que.back().f<a)
		{
			twok[que.back().s][0] = i;
			summ[que.back().s][0] = b;
			que.pop_back();
		}
		que.push_back(mp(a, i));
	}
	while (que.size()) {twok[que.back().s][0] = n+1, summ[que.back().s][0] = INF; que.pop_back();}
	init2k();
	while (q--)
	{
		input(a); input(b);
		//show2(a,b);
		b-=fountain[a].s;
		if (b<=0) {print(a, '\n'); continue;}
		for (ll k=20; k>=0; --k)
		{
			if (b>summ[a][k])
			{
				b-=summ[a][k];
				a = twok[a][k];
				//show3(k, a,b);
			}
		}
		if (twok[a][0]==n+1) {print(0LL, '\n');}
		else {print(twok[a][0], '\n');}
	}
	return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
fountain.cpp:44:2: note: in expansion of macro 'input'
   44 |  input(n); input(q);
      |  ^~~~~
fountain.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
fountain.cpp:44:12: note: in expansion of macro 'input'
   44 |  input(n); input(q);
      |            ^~~~~
fountain.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
fountain.cpp:48:3: note: in expansion of macro 'input'
   48 |   input(a); input(b);
      |   ^~~~~
fountain.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
fountain.cpp:48:13: note: in expansion of macro 'input'
   48 |   input(a); input(b);
      |             ^~~~~
fountain.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
fountain.cpp:62:3: note: in expansion of macro 'input'
   62 |   input(a); input(b);
      |   ^~~~~
fountain.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
fountain.cpp:62:13: note: in expansion of macro 'input'
   62 |   input(a); input(b);
      |             ^~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4556 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 43608 KB Output is correct
2 Correct 241 ms 43348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4556 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 230 ms 43608 KB Output is correct
9 Correct 241 ms 43348 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 85 ms 27476 KB Output is correct
12 Correct 373 ms 46168 KB Output is correct
13 Correct 200 ms 45908 KB Output is correct
14 Correct 162 ms 45200 KB Output is correct
15 Correct 121 ms 46932 KB Output is correct