oj.uz

Submission #87182

# Submission time Handle Problem Language Result Execution time Memory
87182 2018-11-29T22:42:45 Z jasony123123 Deda (COCI17_deda) C++11
60 / 140
 1000 ms 29204 KB 
#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];

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() {
//	io();
	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:85: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:86: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
60.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5028 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 25 ms 5312 KB Output is correct
4 Execution timed out 1066 ms 18652 KB Time limit exceeded
5 Execution timed out 1066 ms 22336 KB Time limit exceeded
6 Execution timed out 1063 ms 26004 KB Time limit exceeded
7 Execution timed out 1080 ms 29204 KB Time limit exceeded