| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 993511 | wood | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
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>
using namespace std;
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
struct segtree
{
int size = 1, ops[(int)1e6] = {0};
segtree(int n){while(size<n) size*=2;}
void upd(int l, int r){
upd(l,r,0,0,size);
}
void upd(int l, int r, int x, int lx, int rx) {
if(lx>=r||rx<=l) return;
if(lx>=l&&rx<=r){
ops[x]++;
return;
}
int m = (rx+lx)/2;
upd(l,r,2*x+1,lx,m);
upd(l,r,2*x+2,m,rx);
}
int get(int i){
return get(i,0,0,size);
}
int get(int i, int x, int l, int r){
if(r-l==1) return ops[x];
int m = (r+l)/2;
if(i<m) return get(i,2*x+1,l,m)+ops[x];
else return get(i,2*x+2,m,r)+ops[x];
}
};
int main()
{
fast_cin();
#ifndef ONLINE_JUDGE
#ifdef _WIN32
freopen("input.in", "r", stdin);
freopen("input.out", "w", stdout);
#endif
#endif
int n; cin>>n;
p32 arr [n];
for(p32 & sub : arr){
cin>>sub.fi>>sub.se;
}
sort(arr,arr+n);
segtree sgt(1e5);
for (size_t i = 0; i < n; i++)
{
int left = arr[i].fi-arr[i].se;
int l = -1, r = arr[i].fi;
while(r-l>1){
int m = (r+l)/2;
if(sgt.get(m)>=sgt.get(left)) l = m;
else r = m;
}
int done = 0;
if(r<arr[i].fi){
sgt.upd(r,arr[i].fi);
done = arr[i].fi - r;
}
l = -1, r = arr[i].fi;
while(r-l>1){
int m = (r+l)/2;
if(sgt.get(m)>sgt.get(left)) l = m;
else r = m;
}
sgt.upd(r,r-done+arr[i].se);
}
ll res = 0;
for (size_t i = 0; i < 1e5; i++)
{
ll x = sgt.get(i);
res+=x*(x-1)/2;
}
cout<<res<<'\n';
return 0;
}