Submission #1260768

#TimeUsernameProblemLanguageResultExecution timeMemory
1260768PlayVoltzSails (IOI07_sails)C++20
30 / 100
1097 ms14404 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> #include <random> #include <chrono> #include <fstream> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second struct node{ int s, e, m, val; node *l, *r; node(int S, int E){ s = S, e = E, m = (s+e)/2; val=0; if (s!=e){ l = new node(s, m); r = new node(m+1, e); } } void up(int ind, int nv){ if (s==e)val+=nv; else{ if (ind<=m)l->up(ind, nv); else r->up(ind, nv); val = min(l->val, r->val); } } int lbs(int i){ if (s==e){ if (val&&s<=i)return s; return -1; } int res=r->lbs(i); if (res==-1)return l->lbs(i); return res; } int rbs(int i){ if (s==e){ if (val&&s>=i)return s; return LLONG_MAX/2; } int res=l->rbs(i); if (res==LLONG_MAX/2)return r->rbs(i); return res; } int query(int i){ if (s==e)return val; if (i<=m)return l->query(i); return r->query(i); } }*st; int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, ans=0; cin>>n; vector<pii> vect(n); st = new node(0, 100005); for (int i=0; i<n; ++i)cin>>vect[i].fi>>vect[i].se; sort(vect.begin(), vect.end()); for (int i=0; i<n; ++i){ int left=max(1ll, st->lbs(vect[i].fi-vect[i].se+1)), right=min(100005ll, st->rbs(vect[i].fi-vect[i].se+1)), c=min(right-vect[i].fi+vect[i].se-1, vect[i].se); st->up(left, 1); st->up(left+c, -1); if (right<=vect[i].fi){ st->up(right, 1); st->up(vect[i].fi+1, -1); } } for (int i=1, sum=0; i<=n; ++i)sum+=st->query(i), ans+=sum*(sum-1)/2; cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...