oj.uz

Submission #631998

# Submission time Handle Problem Language Result Execution time Memory
631998 2022-08-19T09:39:49 Z gagik_2007 Fountain (eJOI20_fountain) C++17
30 / 100
 1500 ms 5488 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef double ld;
typedef ll itn;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;

struct Vaz {
	int ind;
	ll c;
	ll d;
	int nxt;
	Vaz(int i, int vv, int dd) {
		ind = i;
		c = vv;
		d = dd;
		nxt = -1;
	}
};

vector<Vaz>a;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		ll x, y; cin >> x >> y;
		Vaz vaz(i, y, x);
		a.push_back(vaz);
	}
	set<pair<int, int>>cur;
	vector<pair<int, int>>to_del;
	for (int i = 0; i < n; i++) {
		for (auto it = cur.begin(); it != cur.end(); it++) {
			if ((*it).ff < a[i].d) {
				a[(*it).ss].nxt = i;
				to_del.push_back((*it));
			}
			else break;
		}
		for (auto x : to_del) {
			cur.erase(x);
		}
		to_del.clear();
		cur.insert({ a[i].d,i });
	}
	for (int i = 0; i < m; i++) {
		ll v, r;
		cin >> r >> v;
		r--;
		v -= a[r].c;
		while (r != -1 && v > 0) {
			r = a[r].nxt;
			if (r == -1)break;
			v -= a[r].c;
		}
		cout << r + 1 << endl;
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 380 KB Output is correct
5 Correct 7 ms 400 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 5488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 380 KB Output is correct
5 Correct 7 ms 400 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Execution timed out 1586 ms 5488 KB Time limit exceeded
9 Halted 0 ms 0 KB -