/******************************
* author : @yayayaya *
* date : 21 / 10 / 2022 *
******************************/
/* (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ */
/*
/^--^\ /^--^\ /^--^\
\____/ \____/ \____/
/ \ / \ / \
| | | | | |
\__ __/ \__ __/ \__ __/
|^|^|^|^|^|^|^|^|^|^|^|^\ \^|^|^|^/ /^|^|^|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|
| | | | | | | | | | | | |\ \| | |/ /| | | | | |\ \| | | | | | | | | | | |
| | | | | | | | | | | | |/ /| | |\ \| | | | | |/ /| | | | | | | | | | | |
| | | | | | | | | | | | |\/ | | | \/| | | | | |\/ | | | | | | | | | | | |
#########################################################################
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | */
/*******************************************************************************************
* ################################################################# *
* # _` # *
* # _ooOoo_ # *
* # o8888888o # *
* # 88" . "88 # *
* # (| -_- |) # *
* # O\ = /O # *
* # ____/`---'\____ # *
* # .' \| |// `. # *
* # / \||| : |||// \ # *
* # / _||||| -:- |||||_ \ # *
* # | | \ - /'| | | # *
* # | \_| `\`---'// |_/ | # *
* # \ .-\__ `-. -'__/-. / # *
* # ___`. .' /--.--\ `. .'___ # *
* # ."" '< `.___\_<|>_/___.' _> \"". # *
* # | | : `- \`. ;`. _/; .'/ / .' ; | # *
* # \ \ `-. \_\_`. _.'_/_/ -' _.' / # *
* #=============`-.`___`-.__\ \___ /__.-'_.'_.-'=================# *
* `=--=-' *
* *
* /\_/\* *
* ( -.-) *
* _.-/`) / >O \>1 _.-/`) *
* // / / ) // / / ) *
* .=// / / / ) /\_/\ /\_/\ .=// / / / ) *
* //`/ / / / / ( -.-) ( -.-) //`/ / / / / *
* // / ` / / >O \>1 / >O \>1 // / ` / *
* \ / \ / *
* )) .' /\_/\ /\_/\ /\_/\ )) .' *
* // / ( -.-) ( -.-) ( -.-) // / *
* / / >O \>1 / >O \>1 / >O \>1 / *
* *
*******************************************************************************************/
#include <bits/stdc++.h>
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize ("O3,unroll-loops,no-stack-protector")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))
#define FOR(i_, a_, b_) for(int i_ = (int) (a_); i_ <= (int) (b_); ++i_)
#define FORD(i_, a_, b_) for(int i_ = (int) (a_); i_ >= (int) (b_); --i_)
#define db(val) "["#val" = "<<(val)<<"] "
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
template<class X, class Y> bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template<class X, class Y> bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 2e5 + 11;
const int LOG = (int) 20;
const ii dxy8[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1} };
const ii dxy4[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
int maxSize;
struct query_{
int op, x, y;
};
struct FenwickTree{
set<int> bit[maxn];
void Update(int x, int y){
while(x <= maxSize){
bit[x].insert(y);
x += (x & -x);
}
}
int Get(int x, int y){
int ans = -1;
while(x){
auto it = bit[x].lower_bound(y);
if(it != bit[x].end() && (*it >= y)){
if((ans == -1) || (ans > *it)) ans = *it;
}
x -= (x & -x);
}
return ans;
}
} BIT;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TASK "DEDA"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int n, q; cin >> n >> q;
vector<query_> qry;
vector<int> cpr;
FOR(i, 1, q){
char op; int x, y; cin >> op >> x >> y;
if(op == 'M'){
qry.PB({0, x, y});
}
else{
qry.PB({1, x, y});
}
cpr.PB(x);
}
sort(ALL(cpr)); cpr.resize(unique(ALL(cpr)) - cpr.begin());
maxSize = (int) cpr.size();
FOR(i, 0, q - 1){
if(qry[i].op == 0){
int u = lower_bound(ALL(cpr), qry[i].x) - cpr.begin() + 1;
BIT.Update(u, qry[i].y);
}
else{
int u = lower_bound(ALL(cpr), qry[i].x) - cpr.begin() + 1;
cout << BIT.Get(u, qry[i].y) << "\n";
}
}
return 0;
}
/// CONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACO ///
Compilation message
deda.cpp: In function 'int main()':
deda.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
deda.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10068 KB |
Output is correct |
| 4 |
Correct |
147 ms |
18300 KB |
Output is correct |
| 5 |
Correct |
575 ms |
44376 KB |
Output is correct |
| 6 |
Correct |
462 ms |
36924 KB |
Output is correct |
| 7 |
Correct |
393 ms |
33164 KB |
Output is correct |
