#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define p push
#define ins insert
#define t top
#define fr front
#define T1 10
#define T2 100
#define T3 1000
#define T4 10000
#define T5 100000
#define T6 1000000
#define H1 11
#define H2 105
#define H3 1010
#define H4 10010
#define H5 100010
#define H6 1000010
#define woof 31051
#define mod 998244353
#define MOD 1000000007
#define lnf 0
#define inf 1069999999
#define INF 2099999999
#define LNF 5e18
#define tc(T) template <class T>
#define tcc(S, T) template <class S, class T>
#define tccc(S, T, U) template <class S, class T, class U>
using namespace std;
mt19937 mr(time(0));
typedef long long int ll;
typedef string str;
typedef double dbl;
struct LL {
static ll m; // set to LNF for nomod
long long int val;
LL(ll v) {val=reduce(v);};
LL(int v) {val=reduce((ll)v);};
LL() {val=0;};
~LL(){};
LL(const LL& l) {val=l.val;};
LL& operator=(int l) {val=l; return *this;}
LL& operator=(ll l) {val=l; return *this;}
LL& operator=(LL l) {val=l.val; return *this;}
static void setMod(ll m) { assert(m); LL::m = m; }
static long long int reduce(ll x, ll md = m) {
x %= md;
while (x >= md) x-=md;
while (x < 0) x+=md;
return x;
}
bool operator<(const LL& b) { return val<b.val; }
bool operator<=(const LL& b) { return val<=b.val; }
bool operator!=(const LL& b) { return val!=b.val; }
bool operator==(const LL& b) { return val==b.val; }
bool operator>=(const LL& b) { return val>=b.val; }
bool operator>(const LL& b) { return val>b.val; }
LL operator+(const LL& b) { return LL(val+b.val); }
LL operator+(const ll& b) { return (*this+LL(b)); }
LL& operator+=(const LL& b) { return (*this=*this+b); }
LL& operator+=(const ll& b) { return (*this=*this+b); }
LL operator-(const LL& b) { return LL(val-b.val); }
LL operator-(const ll& b) { return (*this-LL(b)); }
LL& operator-=(const LL& b) { return (*this=*this-b); }
LL& operator-=(const ll& b) { return (*this=*this-b); }
LL operator*(const LL& b) { return LL(val*b.val); }
LL operator*(const ll& b) { return (*this*LL(b)); }
LL& operator*=(const LL& b) { return (*this=*this*b); }
LL& operator*=(const ll& b) { return (*this=*this*b); }
static LL exp(const LL& x, const ll& y){
ll z = y;
z = reduce(z,m-1);
LL ret = 1;
LL w = x;
while (z) {
if (z&1) ret *= w;
z >>= 1; w *= w;
}
return ret;
}
LL& operator^=(ll y) { return (*this=LL(val^y)); }
LL operator/(const LL& b) { return ((*this)*exp(b,-1)); }
LL operator/(const ll& b) { return (*this/LL(b)); }
LL operator/=(const LL& b) { return ((*this)*=exp(b,-1)); }
LL& operator/=(const ll& b) { return (*this=*this/LL(b)); }
}; ostream& operator<<(ostream& os, const LL& obj) { return os << obj.val; }
ll LL::m = MOD;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<int,LL> piL;
typedef pair<ll,ll> pll;
typedef pair<LL,LL> pLL;
typedef pair<dbl,dbl> pdd;
using namespace std;
// sacrilege
#define bts(a,x,b) ((a<x)&&(x<b))
#define btw(a,x,b) ((a<=x)&&(x<=b))
#define F0(x,n) for(ll x = 0; x < n; ++x)
#define Fr(x,L,R) for(ll x = L; x < R; ++x)
#define R0(x,n) for(ll x = n-1; x >= 0; --x)
#define F1(x,n) for(ll x = 1; x <= n; ++x)
#define FR(x,L,R) for(ll x = L; x <= R; ++x)
#define R1(x,n) for(ll x = n; x >= 1; --x)
#define RR(x,L,R) for(ll x = R; x >= L; --x)
#define Rr(x,L,R) for(ll x = R-1; x >= L; --x)
#define FE(x,ls) for(auto x : ls)
#define FER(x,ls) for(auto &x : ls)
#define srt(x) sort(x.begin(),x.end())
#define srtc(x,c) sort(x.begin(),x.end(),c)
#define rev(x) reverse(x.begin(),x.end())
#define UB upper_bound
#define LB lower_bound
#define ub(x,v) upper_bound(x.begin(),x.end(),v)
#define lb(x,v) lower_bound(x.begin(),x.end(),v)
#define bs(x,v) binary_search(x.begin(),x.end(),v)
#define dst(x,y) (ll)distance(x,y)
#define nlt(x,v) (ll)dst(x.begin(),lb(x,v))
#define nle(x,v) (ll)dst(x.begin(),ub(x,v))
ll cases,N,M,Q,K,X,Y;
//ifstream fin("exercise.in");
//ofstream fout("exercise.out");
ll rd() {ll x;cin>>x; return x;}
dbl rdd() {dbl x;cin>>x; return x;}
str rds() {str x;cin>>x; return x;}
tc(T) void rds(char* S, T* sz) {*sz=strlen(strcpy(S,rds().c_str()));}
tc(T) void rG(int sz, vector<vector<T>>& adj, int E = -18852946) {
if (E == -18852946) E = sz-1;
adj.clear();
F0(i,sz+1) adj.pb(vector<T>());
F0(i,E) {
T a = rd(); T b = rd();
adj[a].pb(b); adj[b].pb(a);
}
}
tcc(S,T) void rdv(vector<S>& vec, T* sz, bool flag = 1) {
if (flag) *sz = rd();
F0(i,*sz) vec.pb(rd());
}
void fl() {cout.flush();}
void ds(int v) { cout << v << " "; }
void ds(ll v) { cout << v << " "; }
void ds(LL v) { cout << v << " "; }
void ds(dbl v) { cout << v << " "; }
void ds(char v) { cout << v << " "; }
void ds(str v) { cout << v << " "; }
void ds(char* v) { cout << v << " "; }
tc(T) void ds(T* v, int t) {
auto x = v;
F0(i,t) ds(*(x++)); cout << endl;
}
tcc(S,T) void ds(pair<S,T> v) {cout << "( "; ds(v.f); cout << ", "; ds(v.s); cout << ") ";}
tc(T) void ds(vector<T> v) { FE(x,v) ds(x); cout << endl; }
tc(T) void panic(T out) { ds(out); exit(0); }
tcc(S,T) bool updmin(S &a, T b) {
S B = (S)b;
if (B < a) {a = B; return 1;}
return 0;
}
tcc(S,T) bool updmax(S &a, T b) {
S B = (S)b;
if (B > a) {a = B; return 1;}
return 0;
}
tcc(S,T) S min(S a, T b) {
S c = a; updmin(c, b); return c;
}
tcc(S,T) S max(S a, T b) {
S c = a; updmax(c, b); return c;
}
// witness
bool witness(LL a, ll d, ll m) {
LL x = LL::exp(a,m);
if (x==LL(1)) return 1;
F0(r,d) {
if (x==LL(-1)) return 1;
x = x*x;
}
return 0;
}
// O(log^3 n) test
bool isPrime(ll x) {
if (x < T6) {
int j = 2;
while (j*j <= x) {
if (x%j==0) return 0;
++j;
}
return 1;
}
ll d = 0;
ll m = 0;
ll y = x;
ll cur = LL::m;
LL::m = x;
bool ret = 1;
while (y>>=1) {
++d; if (y&1) break;
}
m = y;
if (x < 1e12) {
ret = witness(2,d,m)
&& witness(13,d,m)
&& witness(23,d,m)
&& witness(1662803,d,m);
} else {
ret = witness(2,d,m)
&& witness(3,d,m)
&& witness(5,d,m)
&& witness(7,d,m)
&& witness(11,d,m)
&& witness(13,d,m)
&& witness(17,d,m)
&& witness(19,d,m)
&& witness(23,d,m)
&& witness(29,d,m)
&& witness(31,d,m)
&& witness(37,d,m)
&& witness(41,d,m);
}
LL::m = cur;
return ret;
}
#define H H5
#define HH 43
ll gcd(ll a, ll b) {
return b?gcd(b, a % b):a;
}
void precalc() {
}
void reset() {
}
bool cmp(pii a, pii b) {
return (a.s==b.s)?(a.f<b.f):(a.s<b.s);
}
bool debug = 0;
struct Cheese {
ll F(ll a, ll b) {
return a+b;
}
int sz;
vector<ll> ST;
vector<ll> lazy;
void start(int n) {
sz = n;
for (int i = 0; i < 4*n; i++) { ST.pb(0); lazy.pb(0); }
}
void build(ll * A, int idx, int b, int e) {
lazy[idx]=0;
if(b == e) {
ST[idx] = A[b];
} else {
int mid = (b + e) / 2;
build(A, 2*idx, b, mid);
build(A, 2*idx+1, mid+1, e);
ST[idx] = F(ST[2*idx],ST[2*idx+1]);
}
}
void build(ll * A) { build(A, 1, 0, sz-1); }
void update(int idx, int b, int e, int l, int r, ll val) {
if (lazy[idx] != 0) {
ST[idx] += lazy[idx];
if(b != e) {
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
}
lazy[idx] = 0;
}
if ((b > e) || (b > r) || (e < l)) return;
if ((b >= l) && (e <= r)) {
ST[idx] += val;
if (b != e) {
lazy[idx*2] += val;
lazy[idx*2+1] += val;
}
return;
}
int mid = (b + e) / 2;
update(idx*2, b, mid, l, r, val);
update(idx*2 + 1, mid + 1, e, l, r, val);
ST[idx] = F(ST[idx*2],ST[idx*2+1]);
}
void update(int l, int r, ll val) { update(1,0,sz-1,l,r,val); }
ll query(int idx, int b, int e, int l, int r) {
if ((b > e) || (b > r) || (e < l)) return 0;
if (lazy[idx] != 0) {
ST[idx] += lazy[idx];
if (b != e) {
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
}
lazy[idx] = 0;
}
if(b >= l and e <= r) return ST[idx];
int mid = (b + e) / 2;
ll p1 = query(idx*2, b, mid, l, r);
ll p2 = query(idx*2 + 1, mid + 1, e, l, r);
return F(p1,p2);
}
ll query(int l, int r) { return query(1,0,sz-1,l,r); }
ll query(int l) { return query(l,l); }
} ST;
vector<pii> Qs;
void read() {
N=rd();
ST.start(H);
F0(i,N) {
int h = rd(); int k = rd();
Qs.pb({h,k});
}
srt(Qs);
FE(x,Qs) {
int h = x.f; int k = x.s;
int L,R,lm,rm,key;
key = ST.query(h-k);
L = 0, R = h-k;
while (L<R) {
int M = (L+R)>>1;
if (ST.query(M)==key) { R = M; }
else { L = M+1; }
}
lm=L;
L = h-k, R = h-1;
while (L<R) {
int M = (L+R+1)>>1;
if (ST.query(M)==key) { L = M; }
else { R = M-1; }
}
rm=R;
int dist = rm-(h-k);
ST.update(rm+1,h-1,1);
ST.update(lm,lm+dist,1);
}
ll ans = 0;
F0(i,H) {
ll k = ST.query(i);
ans+=k*(k-1)/2;
}
cout << ans << endl;
}
int main() {
precalc();
bool trials = 0;
bool interactive = 0;
if (!interactive) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
if (trials) cases=rd();
else cases=1;
while (cases--) {
read();
}
}
Compilation message
sails.cpp: In function 'void ds(T*, int)':
sails.cpp:120:17: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
120 | #define F0(x,n) for(ll x = 0; x < n; ++x)
| ^~~
sails.cpp:176:5: note: in expansion of macro 'F0'
176 | F0(i,t) ds(*(x++)); cout << endl;
| ^~
sails.cpp:176:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
176 | F0(i,t) ds(*(x++)); cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
6772 KB |
Output is correct |
| 2 |
Correct |
18 ms |
6808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
6828 KB |
Output is correct |
| 2 |
Correct |
17 ms |
6836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
6824 KB |
Output is correct |
| 2 |
Correct |
19 ms |
6824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
6824 KB |
Output is correct |
| 2 |
Correct |
21 ms |
6824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
6824 KB |
Output is correct |
| 2 |
Correct |
25 ms |
6844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
6800 KB |
Output is correct |
| 2 |
Correct |
148 ms |
7384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
7092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
283 ms |
7508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
579 ms |
8204 KB |
Output is correct |
| 2 |
Correct |
493 ms |
9124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
511 ms |
8336 KB |
Output is correct |
| 2 |
Correct |
250 ms |
9020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
640 ms |
8404 KB |
Output is correct |
| 2 |
Correct |
375 ms |
9344 KB |
Output is correct |
