| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 969450 |
2024-04-25T07:33:31 Z |
sano |
Pairs (IOI07_pairs) |
C++14 |
|
361 ms |
77256 KB |
#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;
if (r == 2) {
cin >> x >> y;
}
else {
cin >> x;
y = 0;
}
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
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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
21988 KB |
Output is correct |
| 2 |
Correct |
68 ms |
21472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
350 ms |
77256 KB |
Output is correct |
| 2 |
Correct |
329 ms |
75716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
74948 KB |
Output is correct |
| 2 |
Correct |
172 ms |
45252 KB |
Output is correct |
| 3 |
Correct |
117 ms |
23676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
21780 KB |
Output is correct |
| 2 |
Correct |
78 ms |
22236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
21464 KB |
Output is correct |
| 2 |
Correct |
95 ms |
21988 KB |
Output is correct |
| 3 |
Correct |
95 ms |
21456 KB |
Output is correct |
| 4 |
Correct |
88 ms |
21216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
31844 KB |
Output is correct |
| 2 |
Correct |
305 ms |
44740 KB |
Output is correct |
| 3 |
Correct |
103 ms |
22884 KB |
Output is correct |
| 4 |
Correct |
97 ms |
23248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
21448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
22980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
21192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
