oj.uz

답안 #870160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870160 2023-11-07T06:19:26 Z vjudge1 Deda (COCI17_deda) C++17
0 / 140
 42 ms 65536 KB 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;

#define f first
#define s second
#define mk make_pair
#define int long long
#define dg cout << "------------------" << endl
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 1e6 + 7;
int Point[N], Ans, n, m;
pair<int, int> Ar[N];
ordered_set adj[N];
vector<int> node;
map<int, int> mp;
char Ml[N];

void update(int u, int w) {
	if (u < 1) return;
	adj[u].insert(w), update(u / 2, w);
}
void Segment(int u, int w, int ul, int ur) {
	if (ul >= w) {
		node.push_back(u);
		return;
	}
	if (ur - ul <= 1 || w > ur - 1) return;
	int mid = (ur + ul) / 2;
	Segment(u * 2, w, ul, mid);
	Segment(u * 2 + 1, w, mid, ur);
}
void solve1(int Check, int po) {
	node.clear(), Ans = -1;
	Segment(1, Ar[po].s, 1, (n + 1));
	for (int i = 0; i < node.size(); i++) {
		int l = adj[node[i]].order_of_key(Check + 1);
		if (l > 0) {
			Ans = mp[*adj[node[i]].find_by_order(l - 1)];
			break;
		}
	}
	cout << Ans << "\n";
}
void solve() {
	for (int i = 1; i <= m; i++) {
		if (Ml[i] == 'M') update(Point[Ar[i].s], Ar[i].f);
		if (Ml[i] == 'D') solve1(Ar[i].f, i);
	}
}
void build(int u, int ul, int ur) {
	if (ur - ul <= 1) {
		Point[ul] = u;
		return;
	}
	int mid = (ur + ul) / 2;
	build(u * 2, ul, mid);
	build(u * 2 + 1, mid, ur);
}
void input() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> Ml[i] >> Ar[i].f >> Ar[i].s, mp[Ar[i].f] = Ar[i].s;
}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input(), build(1, 1, (n + 1)), solve();
}

Compilation message

deda.cpp: In function 'void solve1(long long int, long long int)':
deda.cpp:39:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < node.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Runtime error 42 ms 65536 KB Execution killed with signal 9
3 Runtime error 29 ms 65536 KB Execution killed with signal 9
4 Runtime error 30 ms 65536 KB Execution killed with signal 9
5 Runtime error 30 ms 65536 KB Execution killed with signal 9
6 Runtime error 29 ms 65536 KB Execution killed with signal 9
7 Runtime error 29 ms 65536 KB Execution killed with signal 9