Submission #1325889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325889		annn	Deda (COCI17_deda)	C++20	140 / 140	442 ms	45748 KiB

deda

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

#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define mii map<int, int>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define all(a, len) (a) + 1, (a) + len + 1
#define vall(a) (a).begin(), a.end()
const int INF = 4e18;
const int MOD = 1e9 + 7;

int n, q; const int mx = 2e5 + 3;

struct BIT {
	int n;
	set<int> bit[mx];
	BIT(int n_ = mx) {
		n = n_;
	};
	
	void update(int u, int val) {
		int idx = u;
		while (idx <= this->n) {
			bit[idx].insert(val);
			idx += (idx&(-idx));
		}
	}
	
	int get(int p, int b) {
		int idx = p, ans = INF;
		while (idx > 0) {
			auto it = bit[idx].lower_bound(b);
			if (it != bit[idx].end()) ans = min(ans, *it);
			idx -= (idx&(-idx));
		}
		return (ans == INF ? -1 : ans);
	}
} bit;

void TheEminemShow() {
    // if (!(cin >> n >> m)) cerr << "??";
    cin >> n >> q;
	// cerr << "fail = " << cin.fail() << endl;
	// cerr << "bad = " << cin.bad() << endl;
	// cerr << "eof = " << cin.eof() << endl;
}

void Recovery() {
	vector<array<int, 3>> qr; 
	vi nen;
	rep(i, 1, q) {
		char c; int x, a; cin >> c >> x >> a;
		qr.pb({c == 'M', x, a});
		// cerr << (c == 'M') << endl;
		nen.pb(x);
	}
	sort(vall(nen)); nen.erase(unique(vall(nen)), nen.end());
	
	for (auto [t, x, a]: qr) {
		int i = lower_bound(vall(nen), x) - nen.begin() + 1;
		if (t) {
			bit.update(i, a);
		} else {
			cout << bit.get(i, a) << endl;
		}
	}
}

void Kamikaze() {

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int TEST = 1;
    // cin >> TEST;
    while (TEST--) {
        TheEminemShow();
        Recovery();
        Kamikaze();
    }

    return 0;

}

• Subtask 1: 140 / 140