Submission #1281319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281319		nmhung	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	117 ms	8084 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
//#define in ({int x = 0; int c = getchar(), n = 0; for(; !isdigit(c); c = getchar()) n = (c == '-'); for(; isdigit(c); c = getchar()) x = x * 10 + c - '0'; n ? -x : x;})

#define bit(i, mask) (((mask) >> (i)) & 1)
#define on(i, mask) ((mask) | (1LL << (i)))
#define off(i, mask) ((mask) & (~(1LL << (i))))

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define vi vector<int>
#define all(a) (a).begin(), (a).end()
#define len(x) ((int)(x).size())
#define pb push_back
#define endl '\n'

#define name "hopqua"

template<typename T1, typename T2> bool mini(T1 &a, T2 b)
    {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b)
    {if(a < b) a = b; else return 0; return 1;}

const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
const ll  oo  = 1e18l + 7;
const int M   = 5e5 + 6;
const int N   = 2e5 + 6;
const int LOG = 31 - __builtin_clz(N);

struct item{
	int r, h, id;

	bool operator < (const item &it) const{
		if(h != it.h) return h < it.h;
		return r > it.r;
	}
};

int n, q;
item box[N], que[N];
int ans[N];

void inp(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> box[i].r >> box[i].h;
    for(int i = 1; i <= q; i++){
    	cin >> que[i].r >> que[i].h;
    	que[i].id = i;
    }
}

void proc(){
	sort(box + 1, box + n + 1);
    sort(que + 1, que + q + 1);
    deque<int> dq;
	int j = 1;
	for(int i = 1; i <= q; i++){
		while(j <= n && box[j].h <= que[i].h){
			int pos = lower_bound(all(dq), box[j].r) - dq.begin();
			if(pos) dq[pos - 1] = box[j].r;
			else dq.push_front(box[j].r);
			j++;
		}
		ans[que[i].id] = (int)dq.size() - (lower_bound(all(dq), que[i].r) - dq.begin());
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    
    rf

    int test = 1;
    //cin >> test;

    while(test--){
        inp();
        proc();
    }
    
    cerr << "Time elapsed: " << TIME << "s" << endl;
    return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:8:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:81:5: note: in expansion of macro 'rf'
   81 |     rf
      |     ^~
matryoshka.cpp:8:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:81:5: note: in expansion of macro 'rf'
   81 |     rf
      |     ^~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49