Submission #969448

#TimeUsernameProblemLanguageResultExecution timeMemory
969448sanoPairs (IOI07_pairs)C++14
30 / 100
253 ms46024 KiB
#include<iostream> #include<vector> #include<queue> #include<string> #include<fstream> #include<algorithm> #include <iomanip> #include<map> #include <set> #include <math.h> #include <unordered_map> #define ll long long #define For(i, n) for(ll i = 0; i < (ll)n; i++) #define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++) #define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--) #define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--) #define vec vector #define ff first #define ss second #define pb push_back #define pii pair<ll, ll> #define NEK 1000000000000000000 #define mod (1e9 + 7) #define rsz resize #define prv 4 #define D 8 using namespace std; class intervalac { ll n; vec<ll> l, r, in; void update(ll s) { in[s] = in[s * 2] + in[s * 2 + 1]; return; } public: intervalac(vec<ll> a) { n = 1; while (n < a.size()) n *= 2; a.resize(n, 0); l.resize(2 * n); r.rsz(2 * n); in.rsz(2 * n); For(i, n) { in[i + n] = a[i]; l[i + n] = i; r[i + n] = i; } rffor(i, 1, (n - 1)) { l[i] = l[i * 2]; r[i] = r[i * 2 + 1]; update(i); } return; } void zmen(ll a, ll b) { a += n; in[a] += b; a /= 2; while (a) { update(a); a /= 2; } return; } ll daj_suc(ll a, ll b, ll s = 1) { if (a > r[s] || b < l[s]) return 0; if (a <= l[s] && r[s] <= b) return in[s]; return daj_suc(a, b, s * 2) + daj_suc(a, b, s * 2 + 1); } }; struct bod { ll x, y; bool operator <(const bod& other) const { return x < other.x; } }; struct udalost { ll x, y1, y2, ind, typ; bool operator <(const udalost& other) const { if (x == other.x) { return typ < other.typ; } return x < other.x; } }; pii otoc(pii a) { return { (a.ff + a.ss), (a.ss - a.ff) }; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll r, n, d, m; cin >> r >> n >> d >> m; vec<udalost> u; set<ll> suradnice; For(i, n) { ll x, y; cin >> x >> y; ll y1 = y - d; ll y2 = y + d; pii vp = otoc({ x, y }); pii v1 = otoc({ x, y1 }); pii v2 = otoc({ x, y2 }); //typ 0 je pridaj hodnotu udalost prva = { vp.ff, vp.ss, vp.ss, i, 0 }; //typ 1, zisti hodnotu nazaciatku udalost druha = { v1.ff - 1, v1.ss, v2.ss, i, 1 }; //typ 2, zisti hodnotu nakonci na odpocitanie udalost tretia = { v2.ff, v1.ss, v2.ss, i, 2 }; suradnice.insert(vp.ss); suradnice.insert(v1.ss); suradnice.insert(v2.ss); u.push_back(prva); u.push_back(druha); u.push_back(tretia); } vec<ll> sur; unordered_map<ll, ll> sur_ind; for (auto i : suradnice) { sur.push_back(i); sur_ind[i] = sur.size() - 1; } sort(u.begin(), u.end()); vec<ll> sracka(sur.size(), 0); intervalac seg(sracka); vec<ll> odp(n, -1); ll vys = 0; For(i, u.size()) { if (u[i].typ == 0) { seg.zmen(sur_ind[u[i].y1], 1); } if (u[i].typ == 1) { ll h = seg.daj_suc(sur_ind[u[i].y1], sur_ind[u[i].y2]); odp[u[i].ind] = h; } if (u[i].typ == 2) { ll h = seg.daj_suc(sur_ind[u[i].y1], sur_ind[u[i].y2]); vys += (h - odp[u[i].ind] - 1); } } cout << vys / 2 << '\n'; return 0; }

Compilation message (stderr)

pairs.cpp: In constructor 'intervalac::intervalac(std::vector<long long int>)':
pairs.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while (n < a.size()) n *= 2;
      |                ~~^~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...