Submission #1260771

#TimeUsernameProblemLanguageResultExecution timeMemory
1260771PlayVoltzSails (IOI07_sails)C++20
100 / 100
622 ms14408 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 bs(int left, int right){ if (s==left&&e==right)return val; if (right<=m)return l->bs(left, right); if (left>m)return r->bs(left, right); return min(l->bs(left, m), r->bs(m+1, right)); } 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=1, high=vect[i].fi-vect[i].se+2; while (left+1<high){ int mid=(left+high)/2; if (st->bs(mid, vect[i].fi-vect[i].se+1))left=mid; else high=mid; } int low=vect[i].fi-vect[i].se, right=100005; while (low+1<right){ int mid=(low+right)/2; if (st->bs(vect[i].fi-vect[i].se+1, mid))right=mid; else low=mid; } int 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<=100000; ++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...