Submission #998240

#	Time	Username	Problem	Language	Result	Execution time	Memory
998240		vjudge1	Examination (JOI19_examination)	C++14	100 / 100	867 ms	49024 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

struct node {
  int x, y, z, i, val;
};

const int maxn = 1e6 + 5;

struct BIT {
	int b[maxn], n;

	void build(int _n) {
		n = _n;
		fill(b, b + n + 1, 0);
	}
	int lowbit(int x){
		return x & (-x);
	}
	void update(int x, int v){
		for(int i = x; i <= n; i += lowbit(i)){
			b[i] += v;
		}
	}
	int query(int x) {
		int ans = 0;
		for(int i = x; i > 0; i -= lowbit(i)){
			ans += b[i];
		}
		return ans;
	}
} bit;

vector<node> v;
int n, q, ans[maxn];

void cdq(int l, int r) {
	if(l == r) return;
	int m = (l + r) / 2;
	cdq(l, m); cdq(m + 1, r);

	int a = l, b = m + 1, sum = 0;
	vector<pair<int, int>> record;
	vector<node> tmp;
	while(a <= m && b <= r){
		if(v[a].y >= v[b].y){
			int add = v[a].val;
			bit.update(v[a].z, add), sum += add, record.push_back({v[a].z, add}), tmp.push_back(v[a]);
			a++;
		}else{
			ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]);
			b++;
		}
	}
	while(a <= m){
		tmp.push_back(v[a]);
		a++;
	}
	while(b <= r){
		ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]);
		b++;
	}
	for(int i = l; i <= r; i++){
		v[i] = tmp[i - l];
	}
	for(auto i : record) bit.update(i.first, -i.second);
}	

bool comp(node a, node b){
	if(a.x == b.x){
		return a.val > b.val;
	}
	return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x);
}

map<int, int> mp;

void solve() {
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		int a, b, c;
		cin >> a >> b;
		c = a + b;
		mp[a] = true;
		mp[b] = true;
		mp[c] = true;
		v.push_back({a, b, c, i, 1});
	}
	for(int i = n; i < n + q; i++){
		int x, y, z;
		cin >> x >> y >> z;
		mp[x] = true;
		mp[y] = true;
		mp[z] = true;
		v.push_back({x, y, z, i, 0});
	}
	int id = 1;
	for(auto i : mp){
		mp[i.first] = id;
		id++;
	}
	for(int i = 0; i < v.size(); i++){
		v[i].x = mp[v[i].x];
		v[i].y = mp[v[i].y];
		v[i].z = mp[v[i].z];
	}
	bit.build(id);
	sort(v.begin(), v.end(), comp);
	cdq(0, n + q - 1);
	for(int i = n; i < n + q; i++) cout << ans[i] << '\n';
}

int main() {
	file();
	solve();
}

Compilation message (stderr)

examination.cpp: In function 'void solve()':
examination.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
examination.cpp: In function 'void file()':
examination.cpp:9:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   freopen(name".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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