We'd like to thank you all for participating in the contest and hope you enjoyed it. Hope to see you again next year!
The tutorial for problem B will be added soon.
[problem:509001A]
Idea: ninjamayank
The solution to this problem required binary search on answer with 2D prefix sum. First we binary search on the threshold. For a chosen threshold we create a new grid with values greater than or equal to $$$k$$$, set to $$$1$$$, and others to $$$0$$$. Next, we make a 2D prefix grid of size $$$n$$$ x $$$n$$$ for the new matrix containing values $$$0$$$ and $$$1$$$. Now we iterate over all possible $$$k$$$ x $$$k$$$ grids and get the sum using the prefix matrix. If the sum equals $$$k^2$$$ the chosen threshold is valid. We can continue the search for the maximum threshold further according to the validity of the chosen one.
The overall time-complexity is $$$O(n^2 \cdot log(10^{9}))$$$
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void ninjamayank(){
ll n,k;
cin >> n >> k;
vector<vector<ll>> grid(n,vector<ll>(n));
for(ll i = 0;i < n;i++){
input(grid[i]);
}
ll low = 0, high = 1e18;
ll ans = -1;
while(low <= high){
ll mid = (low + high) / 2;
vector<vector<ll>> mat(n,vector<ll>(n));
for(ll i = 0;i < n;i++){
for(ll j = 0;j < n;j++){
mat[i][j] = (grid[i][j] >= mid);
}
}
vector<vector<ll>> pref(n,vector<ll>(n));
for(ll i = 0;i < n;i++){
for(ll j = 0;j < n;j++){
pref[i][j] = mat[i][j] + (i - 1 >= 0 ? pref[i - 1][j] : 0) + (j - 1 >= 0 ? pref[i][j - 1] : 0) - (i - 1 >= 0 && j - 1 >= 0 ? pref[i - 1][j - 1] : 0);
}
}
bool flag = false;
for(ll i = k - 1;i < n;i++){
for(ll j = k - 1;j < n;j++){
ll sum = pref[i][j] - (i - k >= 0 ? pref[i - k][j] : 0) - (j - k >= 0 ? pref[i][j - k] : 0) + (i - k >= 0 && j - k >= 0 ? pref[i - k][j - k] : 0);
if(sum == k * k){
flag = 1;
break;
}
}
}
if(flag){
ans = mid;
low = mid + 1;
}else{
high = mid - 1;
}
}
cout << ans << nline;
}
int main(){
// #ifndef ONLINE_JUDGE
// //for getting input from input1.txt
// freopen("input1.txt", "r", stdin);
// //for getting output from output1.txt
// freopen("output1.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); // remove in problems with online query
int testcase = 1;
// cin >> testcase;
int gtc = 1;
while(testcase--){
//cout << "Case #" << gtc << ": ";
ninjamayank();
gtc++;
}
}
[problem:509001B]
Problem by: fsociety00
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 210;
const int MAXF = 210;
int N, F;
int DuM[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int Init[MAXN][MAXF + 1];
int Mat[MAXN][MAXF + 1];
inline int get_day() {
int d, m;
scanf("%d %d", &d, &m);
--d, --m;
for (int i = 0; i < m; ++i) d += DuM[i];
return d;
}
int Sol5[MAXF];
int Sol73[MAXF];
int Invert[100];
int superOk = true;
void gauss_solve(int p, int *Sol) {
for (int i = 0; i < N; ++i)
for (int j = 0; j <= F; ++j) Mat[i][j] = Init[i][j] % p;
Invert[0] = 0;
for (int i = 1; i < p; ++i)
for (int j = 1; j < p; ++j)
if ((i * j) % p == 1) Invert[i] = j;
int R = 0;
for (int s = 0; s < F; ++s) {
int index = -1;
for (int i = R; index == -1 && i < N; ++i)
if (Mat[i][s] != 0) index = i;
if (index == -1) continue;
if (R != index)
for (int i = 0; i <= F; ++i) swap(Mat[R][i], Mat[index][i]);
int temp_mat = Invert[Mat[R][s]];
for (int i = 0; i <= F; ++i) Mat[R][i] = (Mat[R][i] * temp_mat) % p;
for (int i = 0; i < N; ++i)
if (i != R) {
int coef = Mat[i][s];
for (int j = 0; j <= F; ++j) {
Mat[i][j] -= coef * Mat[R][j];
Mat[i][j] %= p;
if (Mat[i][j] < 0) Mat[i][j] += p;
}
}
++R;
}
for (int i = 0; i < N; ++i) {
int first = -1;
for (int j = 0; j < F; ++j)
if (Mat[i][j] != 0) {
first = j;
break;
}
if (first == -1) {
if (Mat[i][F] != 0) {
superOk = false;
return;
}
continue;
}
Sol[first] = Mat[i][F];
}
}
int main(void) {
scanf("%d %d", &N, &F);
for (int i = 0; i < N; ++i) {
int a = get_day();
int b = get_day();
for (int j = 0; j < F; ++j) scanf("%d", Init[i] + j);
Init[i][F] = ((b - a) % 365 + 365) % 365;
}
gauss_solve(5, Sol5);
gauss_solve(73, Sol73);
if (!superOk) {
printf("-1\n");
return (0 - 0);
}
for (int i = 0; i < F; ++i) {
int tmp = (146 * Sol5[i] + 220 * Sol73[i]) % 365;
if (tmp == 0) tmp = 365;
printf("%d\n", tmp);
}
return (0);
}
[problem:509001C]
Idea: ninjamayank
Let's take the bitwise xor of all elements of the array. Let's consider a bit special if it is set in the bitwise xor of the array. So from each element in the array let's remove their special bits because they will always contribute to the sum and, therefore are redundant.
Now we need to split the elements into two groups such that the sum of their bitwise xor is maximum. If we choose a group such that its bitwise xor is the maximum possible we can construct, it can be proved that the bitwise xor of the remaining elements is the same as that of the chosen elements. So all we need to find is the maximum bitwise xor we can construct. This can be done using the xor-basis technique
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ll> basis(62);
ll sz = 0;
void insertVector(ll mask) {
for (ll i = 61; i >= 0; i--) {
if((mask & (1ll << i)) == 0) continue;
if (!basis[i]){
basis[i] = mask;
++sz;
return;
}
mask ^= basis[i];
}
}
void ninjamayank(){
ll n;
cin >> n;
vector<ll> v(n);input(v);
ll xr = 0;
for(ll i = 0;i < n;i++){
xr ^= v[i];
}
for(ll i = 0;i < n;i++){
ll num = 0;
for(ll mask = 0;mask < 62;mask++){
if(xr&(1ll << mask)) continue;
if(v[i]&(1ll << mask)){
num ^= (1ll << mask);
}
}
insertVector(num);
}
ll ans = 0;
for(ll i = 61;i >= 0;i--){
if(ans&(1ll << i)) continue;
ans ^= basis[i];
}
for(ll i = 0;i < 62;i++){
if(xr&(1ll << i)) ans ^= (1ll << i);
}
cout << ans + (xr ^ ans);
}
int main(){
// #ifndef ONLINE_JUDGE
// //for getting input from input1.txt
// freopen("input1.txt", "r", stdin);
// //for getting output from output1.txt
// freopen("output1.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); // remove in problems with online query
int testcase = 1;
// cin >> testcase;
int gtc = 1;
while(testcase--){
//cout << "Case #" << gtc << ": ";
ninjamayank();
gtc++;
}
}
[problem:509001D]
Idea: abhaumik24
The solution demands the concept of the convex hull, polygon area, and Prick's theorem. The problem consists of 2 parts, the first part simply asks to find the convex hull of the given points and print them in sorted order.
The second part asks for the minimum difference between the number of lattice points if the polygon obtained in part one is divided into two parts by adding an edge between any two of its vertices. As $$$n ≤ 1000$$$, we can try all the pairs of vertices and calculate the number of lattice points in the two areas using the prick's theorem and further calculate the difference
import sys, threading
import math
from os import path
from collections import deque, defaultdict, Counter
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
from heapq import *
from array import array
from types import GeneratorType
def readInts():
x = list(map(int, (sys.stdin.readline().rstrip().split())))
return x[0] if len(x) == 1 else x
def readList(type=int):
x = sys.stdin.readline()
x = list(map(type, x.rstrip('\n\r').split()))
return x
def readStr():
x = sys.stdin.readline().rstrip('\r\n')
return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456
def bootstrap(f, stack=[]):
def wrappedfunc(*args, **kwargs):
if stack:
return f(*args, **kwargs)
else:
to = f(*args, **kwargs)
while True:
if type(to) is GeneratorType:
stack.append(to)
to = next(to)
else:
stack.pop()
if not stack:
break
to = stack[-1].send(to)
return to
return wrappedfunc
class mydict:
def __init__(self, func=lambda: 0):
self.random = randint(0, 1 << 32)
self.default = func
self.dict = {}
def __getitem__(self, key):
mykey = self.random ^ key
if mykey not in self.dict:
self.dict[mykey] = self.default()
return self.dict[mykey]
def get(self, key, default):
mykey = self.random ^ key
if mykey not in self.dict:
return default
return self.dict[mykey]
def __setitem__(self, key, item):
mykey = self.random ^ key
self.dict[mykey] = item
def getkeys(self):
return [self.random ^ i for i in self.dict]
def __str__(self):
return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'
def lcm(a, b):
return (a*b)//(math.gcd(a,b))
def mod(n):
return n%(1000000007)
def area(p1, p2, p3):
cur = (p2[0] - p1[0])*(p3[1] - p1[1]) - (p2[1] - p1[1])*(p3[0] - p1[0])
return cur
def convex_hull(points):
points = list(set(points))
points.sort()
# print(points)
n = len(points)
if n < 3:
return points
hull = []
for i in range(n):
while len(hull) > 1 and area(hull[-2], hull[-1], points[i]) <= 0:
hull.pop()
hull.append(points[i])
ln = len(hull)
for i in range(n-2, -1, -1):
while len(hull) > ln and area(hull[-2], hull[-1], points[i]) <= 0:
hull.pop()
hull.append(points[i])
hull.pop()
return hull
def solve(t):
# print(f'Case #{t}: ', end = '')
n = readInts()
ar = []
for _ in range(n):
u, v = readInts()
ar.append((u, v))
chull = convex_hull(ar)
m = len(chull)
ans = sorted(chull)
print(m)
for x, y in ans:
print(x, y)
area = 0
total_bndr = 0
for i in range(m):
x1, y1 = chull[i%m]
x2, y2 = chull[(i+1)%m]
area += (x1*y2) - (x2*y1)
total_bndr += math.gcd(abs(x2-x1), abs(y2-y1))
area = abs(area)
total_lat = (area - total_bndr)//2 + 1
cost = float('inf')
for i in range(m):
a1 = 0
pref_bndr = 0
x1, y1 = chull[i]
cur = 0
for j in range(i+1, m):
if i == 0 and j == m-1:
break
x2, y2 = chull[j]
x_prev, y_prev = chull[j-1]
cur += (y2*x_prev) - (x2*y_prev)
g = math.gcd(abs(x2-x_prev), abs(y2-y_prev))
pref_bndr += g
cur_bndr = math.gcd(abs(x2-x1), abs(y2-y1))
if j-1 != i:
a1 = cur + ((x2*y1) - (x1*y2))
a1 = abs(a1)
n1 = (a1 - pref_bndr - cur_bndr)//2 + 1
n2 = total_lat - n1 - (cur_bndr-1)
cost = min(cost, abs(n2-n1))
print(cost)
def main():
t = 1
if path.exists("/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt"):
sys.stdin = open("/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt", 'r')
sys.stdout = open("/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/output.txt", 'w')
# sys.setrecursionlimit(100000)
t = readInts()
for i in range(t):
solve(i+1)
if __name__ == '__main__':
main()
[problem:509001E]
Idea: ninjamayank
Since the queries are offline, we can first generate the tree by iterating all type $$$1$$$ queries first. Then the problem becomes standard. We can apply the Euler tour on the tree and can answer each query in constant time. Overall time complexity: $$$O(n)$$$
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ll> tin(N), tout(N);
ll timer = 0;
void euler(ll u, ll p, vector<vector<ll>> &g){
tin[u] = timer++;
for(auto &child : g[u]){
if(child == p) continue;
euler(child,u,g);
}
tout[u] = timer++;
}
bool check(ll l, ll r){
return (tin[l] < tin[r] && tout[l] > tout[r]);
}
void ninjamayank(){
ll n,q;
cin >> n >> q;
vector<vector<ll>> g(n);
vector<pair<ll, ll>> queries;
while(q--){
ll type,l,r;
cin >> type >> l >> r;
--l;--r;
if(type == 1){
g[l].pb(r);
g[r].pb(l);
}else{
queries.pb({l,r});
}
}
euler(0,-1,g);
for(auto &p : queries){
ll l = p.fr, r = p.sc;
cout << (check(l,r) ? "Yes" : "No") << nline;
}
}
int main(){
// #ifndef ONLINE_JUDGE
// //for getting input from input1.txt
// freopen("input1.txt", "r", stdin);
// //for getting output from output1.txt
// freopen("output1.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); // remove in problems with online query
int testcase = 1;
// cin >> testcase;
int gtc = 1;
while(testcase--){
//cout << "Case #" << gtc << ": ";
ninjamayank();
gtc++;
}
}
[problem:509001F]
Idea: ninjamayank
For the solution to the problem, you can iterate through the string and store characters with different parities in 2 different multisets. For constructing the lexicographically minimal string, for each index, if the character at that index is of odd parity, replace it with the minimum odd parity character in the respective multiset and remove the same from the multiset. The same goes for indices with even parity characters. This would result in the final lexicographically minimal string possible
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void ninjamayank(){
ll n;
string s;
cin >> n >> s;
multiset<char> mst1,mst2;
for(auto &x : s){
ll val = x - 'a';
if(val%2 == 0){
mst1.insert(x);
}else{
mst2.insert(x);
}
}
for(auto &x : s){
ll val = x - 'a';
if(val%2 == 0){
x = *mst1.begin();
mst1.erase(mst1.begin());
}else{
x = *mst2.begin();
mst2.erase(mst2.begin());
}
}
cout << s << nline;
}
int main(){
// #ifndef ONLINE_JUDGE
// //for getting input from input1.txt
// freopen("input1.txt", "r", stdin);
// //for getting output from output1.txt
// freopen("output1.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); // remove in problems with online query
int testcase = 1;
cin >> testcase;
int gtc = 1;
while(testcase--){
//cout << "Case #" << gtc << ": ";
ninjamayank();
gtc++;
}
}
[problem:509001G]
Idea: ninjamayank
As mentioned a queen can attack row-wise, column-wise, and in diagonals. Hence they will be attacking each other if they are in the same row, same column, or in the same diagonal.
- To check if the queens are in the same row, we need to verify if $$$y1=y2$$$.
- To check if the queens are in the same column, we need to verify if $$$x1=x2$$$.
- For diagonals, there are two cases. If the queens lie on a diagonal from top-left to bottom-right, then $$$|x1−x2|=|y1−y2|$$$. If the queens lie on a diagonal from top-right to bottom-left, then $$$x1+x2=y1+y2$$$.
If any of the above conditions are met, the queens will be attacking each other.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void ninjamayank(){
ll x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
if(x1 == x2 || y1 == y2){
cout << "Yes" << nline;
return;
}
if(x1 + y1 == x2 + y2){
cout << "Yes" << nline;
return;
}
if(x1 - y1 == x2 - y2){
cout << "Yes" << nline;
return;
}
cout << "No" << nline;
}
int main(){
// #ifndef ONLINE_JUDGE
// //for getting input from input1.txt
// freopen("input1.txt", "r", stdin);
// //for getting output from output1.txt
// freopen("output1.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); // remove in problems with online query
int testcase = 1;
cin >> testcase;
int gtc = 1;
while(testcase--){
//cout << "Case #" << gtc << ": ";
ninjamayank();
gtc++;
}
}
[problem:509001H]
Idea: ninjamayank
The solution to this problem uses segment tree. First, for constraints of $$$h_i$$$, as only the relative order of the values matter and not value itself and as $$$n \le 2 \cdot 10^5$$$ we can reduce the values of $$$h_i$$$ up to $$$2 \cdot 10^5$$$. We sort the values of $$$h_i$$$ and assign the smallest value as $$$1$$$, the second smallest value as $$$2$$$, and so on. As there can be at most $$$2 \cdot 10^5$$$ unique integers the max value of $$$h'_i$$$ is $$$2 \cdot 10^5$$$.
Next for bad trees, we can make a segment tree with its data being the frequency of elements seen so far. We iterate the array from beginning to end and get the sum query of the segment tree from $$$h'_i + 1$$$ to $$$n$$$ and the result will be the number of bad trees for the index $$$i$$$. After the query, we increment the frequency of $$$h'_i$$$ by 1.
We do the same for good trees but iterate the array in the reverse order.
Overall time-complexity: $$$O(n\cdot log(n))$$$
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct segtree{
vector<ll> seg;
vector<ll> lazy;
vector<bool> cLazy;
ll size;
void init(ll n){
size = 1;
while(size < n){
size *= 2;
}
seg.assign(4*size,0ll);
lazy.assign(4*size,0ll);
cLazy.assign(4*size,false);
}
ll apply(ll x1, ll x2){
return (x1 + x2);
}
void propagate(ll ind, ll low, ll high)
{
if(low != high)
{
cLazy[2*ind + 1] = 1;
cLazy[2*ind + 2] = 1;
lazy[2*ind + 1] += lazy[ind];
lazy[2*ind + 2] += lazy[ind];
}
seg[ind] += lazy[ind];
lazy[ind] = 0;
cLazy[ind] = 0;
}
void build(vector<ll> &v, ll ind, ll low, ll high){
if(low == high){
seg[ind] = v[low];
return;
}
ll mid = (low + high) >> 1;
build(v,2*ind + 1,low,mid);
build(v,2*ind + 2,mid + 1,high);
seg[ind] = apply(seg[2*ind + 1],seg[2*ind + 2]);
}
void update(ll ind, ll low, ll high, ll l, ll r, ll val){
if(cLazy[ind]){
propagate(ind,low,high);
}
if(high < l || low > r){
return;
}
if(l <= low && r >= high){
cLazy[ind] = 1;
lazy[ind] += val;
propagate(ind,low,high);
return;
}
ll mid = (low + high) >> 1;
update(2*ind + 1,low,mid,l,r,val);
update(2*ind + 2,mid + 1,high,l,r,val);
seg[ind] = apply(seg[2*ind + 1],seg[2*ind + 2]);
}
ll query(ll ind, ll low, ll high, ll l, ll r){
if(cLazy[ind]){
propagate(ind,low,high);
}
if(high < l || low > r){
return 0;
}
if(low >= l && high <= r){
return seg[ind];
}
ll mid = (low + high) >> 1;
ll left = query(2*ind + 1,low,mid,l,r);
ll right = query(2*ind + 2,mid + 1,high,l,r);
return apply(left,right);
}
};
void ninjamayank(){
ll n;
cin >> n;
vector<ll> v(n);input(v);
segtree st1;
st1.init(n + 1);
map<ll, ll> mp;
for(ll i = 0;i < n;i++){
mp[v[i]] = 0;
}
ll id = 1;
for(auto &it : mp){
it.sc = id++;
}
for(ll i = 0;i < n;i++){
v[i] = mp[v[i]];
}
vector<pair<ll, ll>> res(n);
for(ll i = 0;i < n;i++){
res[i].fr = st1.query(0,0,n,v[i] + 1,n);
st1.update(0,0,n,v[i],v[i],1);
}
segtree st2;
st2.init(n + 1);
for(ll i = n - 1;i >= 0;i--){
res[i].sc = st2.query(0,0,n,v[i] + 1,n);
st2.update(0,0,n,v[i],v[i],1);
}
for(auto &p : res){
cout << p.fr << " " << p.sc << nline;
}
}
int main(){
// #ifndef ONLINE_JUDGE
// //for getting input from input1.txt
// freopen("input1.txt", "r", stdin);
// //for getting output from output1.txt
// freopen("output1.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); // remove in problems with online query
int testcase = 1;
cin >> testcase;
int gtc = 1;
while(testcase--){
//cout << "Case #" << gtc << ": ";
ninjamayank();
gtc++;
}
}
Thank you for participating in AlgoUtsav 2024. We hope, we can provide a better experience next year.
The editorial was superb! Problem C and D were particularly captivating.