In this HackerEarth Not in Range problem solution, You are given (10 to power 6) boxes that are numbered from 1 to (10 to power 6). The value of each box is equal to its number.
There are N ranges and every range consists of two integers L and R denoting that the value of box in the range [L,R] will turn out to be zero.
Find the sum of values of all boxes from 1 to (10 to power 6).
HackerEarth Not in Range problem solution.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define lli long long int
#define br cout<<"n";
#define plli pair<lli,lli>
#define vlli vector<lli>
#define vplli vector<plli>
#define pqlli priority_queue <lli>
#define pqplli priority_queue <plli>
#define mplli map<lli,lli>
#define pb push_back
#define mp make_pair
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define arr(a,n) lli a[n]; fr(i,n){ cin>>a[i]; }
#define arr1(a,n) lli a[n+5]; fr1(i,n){ cin>>a[i]; }
#define print(a,n) fr(i,n) {cout<<a[i]<<" ";} br
#define print1(a,n) fr1(i,n) {cout<<a[i]<<" ";} br
#define printv(vec) for(lli qq=0;qq<vec.size();qq++) {cout<<vec[qq]<<" ";}
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define MAXN 300005
#define mset(a) memset(a,0,sizeof a);
#define MAXNN 1000005
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;
const lli inf = 1e12 + 7;
lli power(lli x, lli y, lli p){ lli res = 1; x = x % p; while (y > 0) {if (y & 1)res = (res%p*x%p) % p;y = y>>1;x = (x%p * x%p) % p;}return res;}
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
lli a[MAXNN];
int main()
{
ios_base::sync_with_stdio(false);
lli i,j,k,l,r,x,y,n,m,t;
mset(a);
cin>>n;
while(n--)
{
cin>>x>>y;
a[x]+=1;
a[y+1]+=-1;
}
for(i=2;i<=1000000;i++)
{
a[i]+=a[i-1];
}
x=0;
for(i=1;i<=1000000;i++)
{
if(a[i]==0)
x+=i;
}
cout<<x<<'n';
return 0;
}
Second solution
#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
LL upd[1000001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<pair<int,int> > v;
LL total = ((1000000LL) * (1000001LL)) / 2;
int n;
assert(cin >> n);
for(int i = 1; i <= n; i++) {
LL l, r;
assert(cin >> l >> r);
upd[l] += 1;
upd[r + 1] += -1;
}
for(int i = 1; i <= 1000000; i++) {
upd[i] += (upd[i - 1]);
}
LL ans = 0;
for(int i = 1; i <= 1000000; i++) {
if(upd[i] == 0)
ans += i;
}
cout << ans;
}