Submission #756597

#	Time	Username	Problem	Language	Result	Execution time	Memory
756597		minhcool	팀들 (IOI15_teams)	C++17	34 / 100	4075 ms	13132 KiB

teams

//#define local
#ifndef local
#include "teams.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n;
ii range[N];

void init(int N, int A[], int B[]){
	n = N;
	for(int i = 1; i <= n; i++) range[i] = {A[i - 1], B[i - 1]};
	sort(range + 1, range + n + 1);
}

int can(int m, int k[]){
	sort(k, k + m);
	int itr = 1;
	priority_queue<int, vector<int>, greater<int>> pq;
	for(int i = 0; i < m; i++){
		while(itr <= n && range[itr].fi <= k[i]){
			pq.push(range[itr].se);
			itr++;	
		}
		//cout << i << " " << itr << "\n";
		for(int j = 0; j < k[i]; j++){
			while(!pq.empty() && pq.top() < k[i]) pq.pop();
			if(pq.empty()) return 0;
			pq.pop();
		//	cout << pq.top().fi << "\n";
			//if(pq.top() < k[i]) return 0;
			//pq.pop();
		}
	}
	//if(itr <= n || !pq.empty()) return 0;
	return 1;
}

//#define local
#ifdef local
void process(){
	int n;
	cin >> n;
	int a[n], b[n];
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	init(n, a, b);
	int q;
	cin >> q;
	while(q--){
		int m;
		cin >> m;
		int k[m];
		for(int i = 0; i < m; i++) cin >> k[i];
		cout << can(m, k) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) process();
}
#endif

Compilation message (stderr)

teams.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
teams.cpp: In function 'int rnd(int, int)':
teams.cpp:27:19: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   27 |  int temp = rng() % (r - l + 1);
      |             ~~~~~~^~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:34:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   34 | void init(int N, int A[], int B[]){
      |           ~~~~^
teams.cpp:20:11: note: shadowed declaration is here
   20 | const int N = 3e5 + 5;
      |           ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23