In this HackerEarth Gori's Crush problem solution, Our web developer Gori is having this huge crush on a girl of his batch. But he is very afraid of proposing her. He does not know whether to do it or not. He told this to his best friend Micro, who is an astrologer. Micro came up with an idea to help Gori. He is having a list of N fortune numbers. He asked Gori two numbers , say a & b (a<=b). He also asked two numbers from Gori's crush, say c & d (c<=d) (The numbers a, b, c & d do not necessarily belong to the list). Then he made two lists from fortune numbers. One having fortune numbers which lie between a & b (inclusive) and one having fortune numbers which lie between c & d (inclusive). Then he counted the number of same elements in the two lists and called it the Matching factor, say m. Micro has a special number say k, now if m >= k, then Gori should propose his crush, otherwise not.
But Gori was not satisified with just one result. So they followed above procedure several times for different values of a, b , c & d and Micro also kept updating the list of fortune numbers. This became a hectic task. So they asked you to make a program for it.
HackerEarth Gori's Crush problem solution.
#include<bits/stdc++.h>
#define ll long long
#define gc getchar_unlocked
#define pc putchar_unlocked
#define repl(i, a, b) for(i=a; i<b; i++)
#define repe(i, a, b) for(i=a; i<=b; i++)
#define per(i, a, b) for(i=a; i>=b; i--)
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
#define pb(x) push_back(x)
#define lt(i) (i<<1)
#define rt(i) ((i<<1)+1)
#define mp(a, b) make_pair(a, b)
#define ln length()
#define sz size()
#define md(a, b) ((a+b)>>1)
#define pii pair<int, int>
#define pll pair<long, long>
#define pLL pair<long long, long long>
#define all(v) v.begin(),v.end()
#define pn pc('\n');
using namespace std;
void sll(ll &x)
{
register char c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
void wll(ll a)
{
if(a<0)
{
pc('-');
a=-a;
}
char snum[100];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while(a!=0);
--i;
while(i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
void wi(int a)
{
if(a<0)
{
pc('-');
a=-a;
}
char snum[100];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while(a!=0);
--i;
while(i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
void wl(long a)
{
if(a<0)
{
pc('-');
a=-a;
}
char snum[100];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while(a!=0);
--i;
while(i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
void sl(long &x)
{
register char c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
void si(int &x)
{
register char c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
ll power(ll a, ll b, ll mod)
{
ll ret = 1 ;
while(b)
{
if(b & 1 ) ret = ret*a % mod;
a = a*a % mod;
b >>= 1 ;
}
return ret;
}
ll gcd(ll a, ll b)
{
while(b) b ^= a ^= b ^= a %= b;
return a;
}
#define N 100100
ll n, a[N], q, k, qry[N][5], bit[N*10];
struct node{
ll type, i, val;
};
ll cnt;
vector<node> v;
bool compare(node a, node b){
return a.val < b.val;
}
void update(ll x, ll val){
for(;x<=cnt; x+=(x&(-x)))
bit[x]+=val;
}
ll query(ll x, ll y){
ll p=0, q=0;
x--;
for(;x;x-=(x&(-x)))
p+=bit[x];
for(;y;y-=(y&(-y)))
q+=bit[y];
return q-p;
}
int main(){
node temp;
ll t, i, j, l;
ll n;
sll(n); sll(q); sll(k);
repe(i,1,n){
sll(a[i]);
temp.val=a[i]; temp.i=i; temp.type=0;
v.pb(temp);
}
repe(i,1,q){
sll(qry[i][0]);
if(!qry[i][0]){
ll x,y;
sll(x);sll(y);
temp.val=y;temp.type=i; temp.i=2;
qry[i][1]=x;qry[i][2]=y;
v.pb(temp);
}
else{
repe(j,1,4){
sll(qry[i][j]);
temp.val=qry[i][j];temp.type=i;temp.i=j;
v.pb(temp);
}
}
}
sort(v.begin(), v.end(), compare);
cnt=0;
repl(i,0,v.sz){
if(!i || (v[i].val != v[i-1].val))cnt++;
if(!v[i].type)
a[v[i].i]=cnt;
else
qry[v[i].type][v[i].i]=cnt;
}
repe(i,1,n)
update(a[i], 1);
repe(i,1,q){
if(!qry[i][0]){
update(a[qry[i][1]], -1);
a[qry[i][1]]=qry[i][2];
update(a[qry[i][1]], 1);
}
else{
ll m, w, x, y, z;
w=qry[i][1];x=qry[i][2];
y=qry[i][3];z=qry[i][4];
if(x < y || z < w)
m=0;
else if(w <= y && z <= x)
m=query(y, z);
else if(y <= w && x <= z)
m=query(w,x);
else if(w <= y && x <= z)
m=query(y, x);
else if(y <= w && z <= x)
m=query(w, z);
if(m >= k)printf("Propose\n");
else printf("Do not propose\n");
}
}
return 0;
}Second solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define si(a) scanf("%d", &a)
#define sl(a) scanf("%lld", &a)
#define pi(a) printf("%d", a)
#define pl(a) printf("%lld", a)
#define pn printf("\n")
ll pow_mod(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1)
res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
struct query {
int type;
int x, y, a, b, c, d;
};
int ar[100005];
map<int, int> mp;
int bit_tree[600005];
void update_bit(int idx, int maxx, int val) {
while(idx <= maxx) {
bit_tree[idx] += val;
idx += (idx & (-idx));
}
}
int query_bit(int idx) {
int res = 0;
while(idx) {
res += bit_tree[idx];
idx -= (idx & (-idx));
}
return res;
}
int main() {
int n, q, k;
si(n); si(q); si(k);
vector<int> v;
for(int i = 0; i < n; ++i) {
si(ar[i]);
v.push_back(ar[i]);
}
vector<query> vq;
query q1;
int type;
while(q--) {
si(type);
q1.type = type;
if(type == 0) {
si(q1.x); si(q1.y);
vq.push_back(q1);
v.push_back(q1.y);
} else {
si(q1.a); si(q1.b); si(q1.c); si(q1.d);
v.push_back(q1.a);
v.push_back(q1.b);
v.push_back(q1.c);
v.push_back(q1.d);
vq.push_back(q1);
}
}
sort(v.begin(), v.end());
mp[v[0]] = 1;
int cnt = 2;
for(int i = 1; i < (int)(v.size()); ++i) {
if(v[i] != v[i - 1]) {
mp[v[i]] = cnt;
cnt++;
}
}
for(int i = 0; i < n; ++i) {
update_bit(mp[ar[i]], cnt, 1);
}
for(int i = 0; i < (int)(vq.size()); ++i) {
if(vq[i].type == 0) {
update_bit(mp[ar[vq[i].x - 1]], cnt, -1);
update_bit(mp[vq[i].y], cnt, 1);
ar[vq[i].x - 1] = vq[i].y;
} else {
int x, y, res;
if(vq[i].c > vq[i].b) {
x = INT_MAX;
y = INT_MIN;
} else if(vq[i].a > vq[i].d) {
x = INT_MAX;
y = INT_MIN;
} else {
x = max(vq[i].a, vq[i].c);
y = min(vq[i].b, vq[i].d);
}
if(y < x) {
res = 0;
} else {
res = query_bit(mp[y]) - query_bit(mp[x] - 1);
}
if(res >= k) {
printf("Propose\n");
} else {
printf("Do not propose\n");
}
}
}
return 0;
}
0 Comments