Submission #1369503

#TimeUsernameProblemLanguageResultExecution timeMemory
1369503gohchingjaykThumper (NOI25_thumper)C++20
100 / 100
411 ms41864 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


#pragma GCC optimize("O3")

using namespace std;

using ll = long long;

#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int INF = 1e18 + 5;
constexpr int MAXN = 500000 + 5;
constexpr int MOD = 1e9 + 7;

int diffDiag[MAXN];
int diffAnti[MAXN];

int trueDiag[MAXN];
int trueAnti[MAXN];

int diagVal[MAXN];
int antiVal[MAXN];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	vector<int> discDiag;
	vector<int> discAnti;

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		int r, c; cin >> r >> c;
		
		diagVal[i] = r - c;
		antiVal[i] = r + c;
		
		discDiag.emplace_back(diagVal[i]);
		discAnti.emplace_back(antiVal[i]);
	}
	
	sort(discDiag.begin(), discDiag.end());
	sort(discAnti.begin(), discAnti.end());
	
	for (int i = 0; i < N; ++i) {
		diagVal[i] = lower_bound(discDiag.begin(), discDiag.end(), diagVal[i]) - discDiag.begin();
		antiVal[i] = lower_bound(discAnti.begin(), discAnti.end(), antiVal[i]) - discAnti.begin();
	}
	
	diffDiag[0] = discDiag[0];
	diffAnti[0] = discAnti[0];
	
	for (int i = 1; i < N; ++i) {
		diffDiag[i] = discDiag[i] - discDiag[i - 1];
		diffAnti[i] = discAnti[i] - discAnti[i - 1];
	}
	
	while (M--) {
		int x; cin >> x;
		
		x--;
		
		int diag = diagVal[x];
		diffDiag[0] -= 2;
		diffDiag[diag] += 2;
		diffDiag[diag + 1] += 2;
		
		int anti = antiVal[x];
		diffAnti[0] -= 2;
		diffAnti[anti] += 2;
		diffAnti[anti + 1] += 2;
	}
	
	int sumDiag = 0;
	int sumAnti = 0;
	for (int i = 0; i < N; ++i) {
		sumDiag += diffDiag[i];
		sumAnti += diffAnti[i];
		
		trueDiag[i] = sumDiag;
		trueAnti[i] = sumAnti;
	}
	
	for (int i = 0; i < N; ++i) {
		int diag = trueDiag[diagVal[i]];
		int anti = trueAnti[antiVal[i]];
		
		int r = (diag + anti) / 2;
		int c = anti - r;
		
		cout << r << ' ' << c << '\n';
	}
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...