제출 #1157215

#제출 시각아이디문제언어결과실행 시간메모리
1157215nguynExamination (JOI19_examination)C++20
100 / 100
287 ms47076 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 1e5 + 5;

int n, q; 
pii a[N]; 

vector<int> c[4 * N], b[4 * N]; 

void mergeSort(int id, int l, int r) {
	if (l == r) {
		b[id].pb(a[l].S); 
		c[id].pb(a[l].F + a[l].S); 
		return; 
	}
	int mid = (l + r) / 2; 
	mergeSort(id * 2, l, mid);
	mergeSort(id * 2 + 1, mid + 1, r); 
	merge(b[id * 2].begin(), b[id * 2].end(), b[id * 2 + 1].begin(), b[id * 2 + 1].end(), back_inserter(b[id])); 
	merge(c[id * 2].begin(), c[id * 2].end(), c[id * 2 + 1].begin(), c[id * 2 + 1].end(), back_inserter(c[id])); 
}	

int get1(int id, int l, int r, int u, int v, int sum) {
	if (a[l].F >= v || a[r].F < u) {
		return 0; 
	}
	if (u <= a[l].F && a[r].F < v) {
		return (r - l + 1) - (lower_bound(c[id].begin(), c[id].end(), sum) - c[id].begin()); 
	}
	int mid = (l + r) / 2; 
	return get1(id * 2, l, mid, u, v, sum) + get1(id * 2 + 1, mid + 1, r, u, v, sum);
}

int get2(int id, int l, int r, int u, int v) {
	if (a[r].F < u) return 0; 
	if (a[l].F >= u) {
		return (r - l + 1) - (lower_bound(b[id].begin(), b[id].end(), v) - b[id].begin()); 
	}
	int mid = (l + r) / 2; 
	return get2(id * 2, l, mid, u, v) + get2(id * 2 + 1, mid + 1, r, u, v); 
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i].F >> a[i].S; 
    }
    sort(a + 1, a + 1 + n); 
    mergeSort(1, 1, n);
    while(q--) {
    	int x, y, z;
    	cin >> x >> y >> z; 

    	cout << get1(1, 1, n, x, max(x, z - y), z) + get2(1, 1, n, max(x, z - y), y) << '\n'; 
    }	
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...