Submission #1243189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243189		Bui_Quoc_Cuong	Examination (JOI19_examination)	C++20	100 / 100	127 ms	8680 KiB

examination

#include<bits/stdc++.h>
using namespace std; 
#define             ll  long long 
#define             fi  first 
#define             se  second
#define         uni(a)  sort(ALL(a)),a.resize(unique(ALL(a))-a.begin()) 
#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    FORN(i,a,b)  for(int i=(int)(a);i<(int)(b);i++)
#define         ALL(a)  a.begin(),a.end()  
#define            tct  template<class T>
tct bool mini(T& a,T b){return (a>b)?a=b,1:0;}
tct bool maxi(T& a,T b){return (a<b)?a=b,1:0;}
const long long INF = 1e18, base = 311, mod = 1e9 + 7; 
const int maxn = 1e6 +  5,oo = 2e9, LG = 20;      

int n, q;
struct bg{
	int x, y, sum;
} a[maxn];

int ans[maxn];

int get_pos(int x, vector <int> &values){
	return lower_bound(ALL(values), x) - values.begin() + 1;
}

int LIM;

struct FenwickTree{
	int bit[maxn];

	void update(int u, int val){
		for(int i = u; i <= LIM; i+=i&-i) bit[i]+= val;
	}

	int get(int u){
		int sum = 0;
		for(int i = u; i; i-=i&-i) sum+= bit[i];
		return sum;
	}

	int get(int l, int r){
		return get(r) - get(l - 1);
	}
} bit1, bit2;

void process(){
	cin >> n >> q;
	FOR(i, 1, n) cin >> a[i].x >> a[i].y, a[i].sum = a[i].x + a[i].y;

	vector <array <int, 4>> qry;
	vector <int> values_x, values_y;

	FOR(i, 1, q){
		int x, y, z; cin >> x >> y >> z;
		values_x.push_back(x);
		values_y.push_back(y);
		qry.push_back({max(z, x + y), x, y, i});
	}
	FOR(i, 1, n) values_x.push_back(a[i].x), values_y.push_back(a[i].y);
	sort(ALL(values_x)); values_x.resize(unique(ALL(values_x)) - values_x.begin());
	sort(ALL(values_y)); values_y.resize(unique(ALL(values_y)) - values_y.begin());
	LIM = max(values_x.size(), values_y.size());

	sort(ALL(qry));
	sort(a + 1, a + 1 + n, [&](bg u, bg v){
		return u.sum < v.sum;
	});
	// FOR(i, 1, n) cout << a[i].sum << "\n";

	int cnt = 0, j = n;
	FORD(i, qry.size() - 1, 0){
		while(j >= 1 && a[j].sum >= qry[i][0]){
			bit1.update(get_pos(a[j].x, values_x), 1);
			bit2.update(get_pos(a[j].y, values_y), 1);
			cnt++;
			j--;
		}
		ans[qry[i][3]] = cnt - bit1.get(get_pos(qry[i][1], values_x) - 1) - bit2.get(get_pos(qry[i][2], values_y) - 1);
	}
	FOR(i, 1, q){
		cout << ans[i] << "\n";
	}
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
    }
    process();
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:91:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57