Submission #652183

#	Time	Username	Problem	Language	Result	Execution time	Memory
652183		4EVER	Deda (COCI17_deda)	C++11	140 / 140	575 ms	44376 KiB

deda

/******************************
*    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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140