Submission #87185

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87185	2018-11-29T22:51:53 Z	jasony123123	Deda (COCI17_deda)	C++11	140 / 140	931 ms	39664 KB

deda

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define MOD1 1000000009LL
#define MOD2 2038072819LL
#define PRI1 610639LL
#define PRI2 949957LL

typedef long long ll;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

struct Ops {
	char md;
	int xy, ab;
	Ops() {}
	Ops(char m, int x, int a) : md(m), xy(x), ab(a) {}
};

int N, Q, M;
Ops allop[200000];

template<int SZ> struct bit2 {
	set<int> data[SZ];
	bit2() {}
	void insert(int R, int d) {
		for (R++; R <= SZ; R += (R&-R))
			data[R].insert(d);
	}
	int query(int R, int d) { // yVals[0...R] min val >= d
		int ret = INT_MAX;
		for (R++; R > 0; R -= (R&-R)) if (!data[R].empty()) {
			auto it = data[R].lower_bound(d);
			if (it != data[R].end())
				ret = min(ret, *it);
		}
		return ret;
	}
};

bit2<175000> bit;

void update(int x, int a) {
	bit.insert(x, a);
}
int query(int y, int b) {
	int ans = bit.query(y, b);
	return ans == INT_MAX ? -1 : ans;
}

//v<int> fakebit[200000];
//
//void update(int x, int a) {
//	fakebit[x].push_back(a);
//}
//int query(int y, int b) {
//	int ans = INT_MAX;
//	FORE(i, 0, y) {
//		for (int j : fakebit[i]) if (j >= b)
//			ans = min(j, ans);
//	}
//	return ans == INT_MAX ? -1 : ans;
//}

void compressCoord() {
	map<int, int> conv;
	FOR(i, 0, Q)
		conv[allop[i].xy] = 0;
	int num = 0;
	for (auto& en : conv)
		en.second = num++;
	FOR(i, 0, Q)
		allop[i].xy = conv[allop[i].xy];
	M = num;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q;
	FOR(i, 0, Q)
		cin >> allop[i].md >> allop[i].xy >> allop[i].ab;
	compressCoord();
	FOR(i, 0, Q) {
		if (allop[i].md == 'M') { // update
			update(allop[i].xy, allop[i].ab);
		}
		else { // query
			cout << query(allop[i].xy, allop[i].ab) << "\n";
		}
	}
	return 0;
}


void io() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// online submission
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message

deda.cpp: In function 'void io()':
deda.cpp:114:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
deda.cpp:115:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8568 KB	Output is correct
2	Correct	9 ms	8692 KB	Output is correct
3	Correct	15 ms	9368 KB	Output is correct
4	Correct	313 ms	19636 KB	Output is correct
5	Correct	931 ms	39664 KB	Output is correct
6	Correct	857 ms	39664 KB	Output is correct
7	Correct	662 ms	39664 KB	Output is correct