This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
vector<int> seg(MAXN<<2,-1);
vector<int> lazy(MAXN<<2, 0);
int rez;
void push(int nod, int tl, int tr)
{
if(lazy[nod] == 0) return;
if(tl != tr)
{
lazy[nod<<1] += lazy[nod];
lazy[nod<<1|1] += lazy[nod];
}
seg[nod] += lazy[nod];
lazy[nod] = 0;
}
int query(int nod, int tl, int tr, int l, int r)
{
push(nod, tl, tr);
if(tl > r || tr < l || tl > tr) return -inf;
if(tl >= l && tr <= r) return seg[nod];
int mid = tl + tr >> 1;
return max(query(nod<<1, tl, mid, l, r), query(nod<<1|1, mid + 1, tr, l, r));
}
void update(int nod, int tl, int tr, int l, int r)
{
push(nod, tl, tr);
if(tl > r || tr < l || tl > tr || l > r) return;
if(tl >= l && tr <= r)
{
lazy[nod]++;
push(nod, tl, tr);
return;
}
int mid = tl + tr >> 1;
update(nod<<1, tl, mid, l, r);
update(nod<<1|1, mid + 1, tr, l, r);
seg[nod] = max(seg[nod<<1], seg[nod<<1|1]);
}
void get(int nod, int tl, int tr, int index)
{
push(nod, tl, tr);
rez = min(rez, seg[nod]);
if(tl == tr) return;
int mid = tl + tr >> 1;
if(index <= mid) get(nod<<1, tl, mid, index);
else get(nod<<1|1, mid + 1, tr, index);
}
signed main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tt = 1;
while(tt--)
{
int n;
cin >> n;
vector<pii> niz(n);
int mx = 0;
for(int i = 0; i < n; i++)
{
cin >> niz[i].fi >> niz[i].sc;
mx = max(mx, niz[i].fi);
}
sort(all(niz));
for(auto x: niz)cout << x.fi << " " << x.sc << endl;
for(int i = 0; i < n; i++)
{
int p = query(1, 1, mx, 1, niz[i].fi);
int tr = niz[i].sc;
int lb = niz[i].fi;
int l = 1, r = niz[i].fi, ub = 1;
while(l <= r)
{
int mid = l + r >> 1;
if(query(1, 1, mx, mid, niz[i].fi) == p)
{
ub = mid;
l = mid + 1;
}
else r = mid - 1;
}
l = 1; r = niz[i].fi;
while(l <= r)
{
int mid = l + r >> 1;
rez = -1;
if(query(1, 1, mx, 1, mid) == p)
{
lb = mid;
r = mid - 1;
}
else l = mid + 1;
}
int pomoc = tr - lb + 1;
update(1, 1, mx, 1, lb - 1);
update(1, 1, mx, niz[i].fi - pomoc + 1, niz[i].fi);
/*
for(int j = 1; j <= mx; j++)
{
rez = inf;
get(1, 1, mx, j);
cout << rez << " ";
}
cout << endl;
*/
}
int finalrez = 0;
for(int j = 1; j <= mx; j++)
{
rez = inf;
get(1, 1, mx, j);
finalrez += (rez) * (rez + 1) / 2;
}
cout << finalrez << endl;
}
}
Compilation message (stderr)
sails.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = tl + tr >> 1;
| ~~~^~~~
sails.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:50:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = tl + tr >> 1;
| ~~~^~~~
sails.cpp: In function 'void get(long long int, long long int, long long int, long long int)':
sails.cpp:61:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = tl + tr >> 1;
| ~~~^~~~
sails.cpp: In function 'int main()':
sails.cpp:92:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = l + r >> 1;
| ~~^~~
sails.cpp:103:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int mid = l + r >> 1;
| ~~^~~
sails.cpp:89:39: warning: variable 'ub' set but not used [-Wunused-but-set-variable]
89 | int l = 1, r = niz[i].fi, ub = 1;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |