제출 #1370888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370888		trandkhoa	Examination (JOI19_examination)	C++20	0 / 100	17 ms	3908 KiB

examination

/**
 *     Author: Tran Dang Khoa
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,l,r) for (int i = (l), _r = (r); i <= _r; i++)
#define REP(i,l,r) for (int i = (l), _r = (r); i < _r; i++)
#define FORN(i,r,l) for (int i = (r), _l = (l); i >= _l; i--)
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define sz(x) (int)x.size()
#define all(v) (v).begin(),(v).end()
#define allVector(v, n) (v).begin() + 1, (v).begin() + (n) + 1
#define segleft (id << 1)
#define segright (id << 1 | 1)
#define tcT template <class T
tcT> bool minimize(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
tcT> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
const int MOD = 1e9+7;

void iofile(string s) {
	freopen((s + ".inp").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct Data {
	int math, info, total, id;
	
	Data(int _math = 0, int _info = 0, int _total = 0, int _id = 0) {
		math = _math;
		info = _info;
		total = _total;
		id = _id;
	}
};

const int N = 1e5;
vector<Data> student, professor;
vector<int> result;
int n, q;

int checksub() {
	bool flag1 = true, flag2 = true, flag3 = true;
	
	FOR(i, 1, n) {
		if (student[i].math > 100000 || student[i].info > 100000) flag1 = false;
	}
	
	FOR(i, 1, q) {
		if (professor[i].math > 100000 || professor[i].info > 100000) flag1 = false;
		if (professor[i].total != 0) flag2 = false;
		if (professor[i].total > 200000) flag3 = false;
	}
	
	if (n <= 3000 && q <= 3000) {
		return 1;
	} else if (flag1 && flag2) {
		return 2;
	} else if (flag1 && flag3) {
		return 3;
	}
	return 4;
}

namespace subtask1 {
	void solve() {
		for (int i = 1, x, y, z; i <= q; i++) {
			x = professor[i].math, y = professor[i].info, z = professor[i].total;
			
			int ans = 0;
			FOR(j, 1, n) {
				if (student[j].math >= x && student[j].info >= y && student[j].total >= z) ans++;
			}
			
			cout << ans << endl;
		}
	}
}

namespace subtask2 {
	struct Fenwick {
		vector<int> bit;
		int n;
		
		Fenwick(int _n) {
			n = _n;
			bit.assign(n + 1, 0);
		}
		
		void update(int idx, int value) {
			while(idx <= n) {
				bit[idx] += value;
				idx += (idx & -idx);
			}
		}
		
		int get(int idx) {
			int res = 0;
			while (idx > 0) {
				res += bit[idx];
				idx -= (idx & -idx);
			}
			return res;
		}
		
		int rangesum(int l, int r) {
			return get(r) - get(l - 1);
		}
	};
	
	void solve() {
		Fenwick tree(N + 5);
		
		sort(allVector(student, n), [](Data &a, Data &b) {
			return a.math > b.math;
		});
		
		sort(allVector(professor, q), [](Data &a, Data &b) {
			return a.math > b.math;
		});
		
		int index = 1;
		for (int i = 1, x, y; i <= q; i++) {
			// vì điểm có thể bằng 0 nên cần +1 để tiện cho việc cập nhật fenwick
			x = professor[i].math + 1, y = professor[i].info + 1;
			
			while (index <= n && student[index].math + 1 >= x) {
				tree.update(student[index].info + 1, 1);
				index++;
			} 

			result[professor[i].id] = tree.rangesum(y, N + 1);
		}
		
		FOR(i, 1, q) cout << result[i] << endl;	
	}
}

namespace subtask3_Treap {
	struct Treap {
		
	};
	
	void solve() {
					
	}
}

namespace subtask3_Vector {
	const int B = 350;
	
	template <int N> struct SqrtBlock {
		int id[N + 1], l[N + 1], r[N + 1];
		vector<vector<int>> value, block;
		int cntblock = 0;
		
		SqrtBlock(int n) {
			value.assign(n + 1, {});
			block.assign(((n + B - 1) / B) + 1, {});
			buildBlock();
		}
		
		void buildBlock() {
			FOR(i, 1, N) {
				if (i % B == 1) cntblock++;
				if (l[cntblock] == 0) l[cntblock] = i;
				r[cntblock] = i;
				id[i] = cntblock; 
			}
		}
		
		void addValue(int index, int x) {
			value[index].insert(lb(all(value[index]), x), x);
			
			int id_block = id[index];
			block[id_block].insert(lb(all(block[id_block]), x), x);
		}
		
		int getans(int lim, int x) {
			int res = 0;
			
			// vì điểm có thể bằng 0 nên cần xét riêng trường hợp này
			if (lim == 0) res += value[0].end() - lb(all(value[0]), x);
			
			FOR(i, 1, cntblock) {
				if (r[i] < lim) continue;
				
				if (l[i] >= lim) {
					res += block[i].end() - lb(all(block[i]), x);
					continue;
				}
				
				FOR(j, l[i], r[i]) {
					if (j >= lim) res += value[j].end() - lb(all(value[j]), x);
				}
			}
			
			return res;
		}
	};
	
	void solve() {
		SqrtBlock<N> block(N);
		
		sort(allVector(student, n), [](Data &a, Data &b) {
			return a.total > b.total;
		});
		
		sort(allVector(professor, q), [](Data &a, Data &b) {
			return a.total > b.total;
		});
		
		int index = 1;

		FOR(i, 1, q) {
			while (index <= n && student[index].total >= professor[i].total) {
				block.addValue(student[index].math, student[index].info);
				index++;
			}
			
			result[professor[i].id] = block.getans(professor[i].math, professor[i].info);
		}
		
		FOR(i, 1, q) cout << result[i] << endl;
	}
}

namespace subtask4 {
	struct Normalize {
		vector<int> value;
		
		void add(int x) {
			value.pb(x);
		} 
		
		void build() {
			sort(all(value));
			value.erase(unique(all(value)), value.end());
		}
		
		int get(int x) {
			return lb(all(value), x) - value.begin() + 1;
		}
	};
	
	struct Fenwick {
		vector<vector<int>> pos;
		vector<vector<int>> bit;
		int n;
		
		Fenwick() {}
		
		void init(int n) {
			this -> n = n;
			pos.assign(n + 1, {});
			bit.assign(n + 1, {});
		}
	
		void fakeadd(int u, int v) {
			int idx = u;
			while (idx <= n) {
				pos[idx].pb(v);
				idx += (idx & -idx);
			}
		}
		
		void fakeget(int u, int v) {
			int idx = u;
			while (idx > 0) {
				pos[idx].pb(v);
				idx -= (idx & -idx); 
			}
		}
		
		void fakequery(int x1, int y1, int x2, int y2) {
			fakeget(x2, y2);
			fakeget(x1 - 1, y2);
			fakeget(x2, y1 - 1);
			fakeget(x1 - 1, y1 - 1);
		}
		
		void compress() {
			FOR(i, 1, n) {
				sort(all(pos[i]));
				pos[i].erase(unique(all(pos[i])), pos[i].end());
				bit[i].assign(sz(pos[i]) + 1, 0);
			}
		}
		
		int getpos(int i, int y) {
			return lb(all(pos[i]), y) - pos[i].begin() + 1;
		}
		
		void add(int x, int y, int value) {
			for (int i = x; i <= n; i += (i & -i)) {
				for (int j = getpos(i, y); j < sz(bit[i]); j += (j & -j)) {
					bit[i][j] += value;
				}
			}
		}
		
		int get(int x, int y) {
			int res = 0;
			for (int i = x; i > 0; i -= (i & -i)) {
				for (int j = getpos(i, y); j > 0; j -= (j & -j)) {
					res += bit[i][j];
				}
			}
			return res;
		}
		
		int query(int x1, int y1, int x2, int y2) {
			return get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
		}
	};
	
	Fenwick fenwick;
	Normalize com;
	
	void compressValue() {
		FOR(i, 1, n) {
			com.add(student[i].math);
			com.add(student[i].info);
		} 
		
		FOR(i, 1, q) {
			com.add(professor[i].math);
			com.add(professor[i].info);
		} 
		
		com.build();
		
		FOR(i, 1, n) {
			student[i].math = com.get(student[i].math);
			student[i].info = com.get(student[i].info);
		} 
		
		FOR(i, 1, q) {
			professor[i].math = com.get(professor[i].math);
			professor[i].info = com.get(professor[i].info);
		} 
		
		fenwick.init(sz(com.value));
	}
	
	void sortValue() {
		sort(allVector(student, n), [](Data &a, Data &b) {
			return a.total > b.total;
		});
		
		sort(allVector(professor, q), [](Data &a, Data &b) {
			return a.total > b.total;
		});
	}
	
	void preCalc() {
		int index = 1;
		FOR(i, 1, q) {
			while (index <= n && student[index].total >= professor[i].total) {
				fenwick.fakeadd(student[index].math, student[index].info);
				index++;
			}
			
			fenwick.fakequery(professor[i].math, professor[i].info, sz(com.value), sz(com.value));
		}
	}
	
	void calcAns() {
		int index = 1;
		FOR(i, 1, q) {
			while (index <= n && student[index].total >= professor[i].total) {
				fenwick.add(student[index].math, student[index].info, 1);
				index++;
			}
			
			result[professor[i].id] = fenwick.query(professor[i].math, professor[i].info, sz(com.value), sz(com.value));
		}
	}
	
	void solve() {
		compressValue();
		sortValue();
		preCalc();
		fenwick.compress();
		calcAns();
		
		FOR(i, 1, q) cout << result[i] << endl;
	}
}

void input() {
	cin >> n >> q;
	
	result.assign(q + 1, 0);
	student.assign(n + 1, Data());
	professor.assign(q + 1, Data());

	for (int i = 1, s, t; i <= n; i++) {
		cin >> s >> t;
		student[i] = {s, t, s + t, i};
	}
	
	for (int i = 1, x, y, z; i <= q; i++) {
		cin >> x >> y >> z;
		professor[i] = {x, y, z, i};
	}
}

void trandkhoa() {
	input();
	
	int subtask = checksub();
	
	if (subtask == 3) {
		subtask3_Vector::solve();	
	}

	/*
	switch (subtask) {
		case 1:
			subtask1::solve();
			break;
		case 2:
			subtask2::solve();
			break;
		case 3:
			subtask3::solve();
			break;
		default:
			subtask4::solve();
	}
	*/
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//iofile("");
	int test = 1;
	//cin >> test;
	while(test--) trandkhoa();
	
	return (0 ^ 0);
}

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

examination.cpp: In function 'void iofile(std::string)':
examination.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen((s + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 0 / 2
• 서브태스크 2: 0 / 20
• 서브태스크 3: 0 / 21
• 서브태스크 4: 0 / 57