| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 762866 |
2023-06-21T21:55:36 Z |
caganyanmaz |
Pairs (IOI07_pairs) |
C++17 |
|
4000 ms |
490600 KB |
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct SegTree1d
{
int n;
vector<int> data, left, right;
SegTree1d(int n) : n(n), data(1, 0), left(1, -1), right(1, -1) {}
void cc(int index)
{
if (left[index] == -1)
{
left[index] = data.size();
data.pb(0);
left.pb(-1);
right.pb(-1);
}
if (right[index] == -1)
{
right[index] = data.size();
data.pb(0);
left.pb(-1);
right.pb(-1);
}
}
void update(int l, int r, int index, int i, int val)
{
if (i >= r || l > i)
return;
if (l + 1 == r)
{
data[index] += val;
return;
}
cc(index);
int m = l+r>>1;
update(l, m, left[index], i, val);
update(m, r, right[index], i, val);
data[index] = data[left[index]] + data[right[index]];
}
int get(int l, int r, int index, int ss, int ee)
{
if (ss >= r || l >= ee)
return 0;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
int lres = 0, rres = 0;
if (left[index] != -1)
lres = get(l, m, left[index], ss, ee);
if (right[index] != -1)
rres = get(m, r, right[index], ss, ee);
return lres + rres;
}
void update(int i, int val) { update(0, n, 0, i, val ); }
int get(int ss, int ee) { return get(0, n, 0, ss, ee); }
};
void solve1d()
{
int n, d, m;
cin >> n >> d >> m;
SegTree1d st(m);
vector<int> v(n);
for (int& i : v)
{
cin >> i;
i--;
st.update(i, 1);
}
int64_t encounters = 0;
for (int i : v)
encounters += st.get(i-d, i+d+1) - 1;
cout << (encounters / 2) << "\n";
}
struct SegTree2d
{
int ll, rr, uu, dd;
vector<int> data;
vector<int> left, right;
vector<int> root;
vector<int> down, up;
SegTree2d (int ll, int rr, int dd, int uu) : ll(ll), rr(rr), uu(uu), dd(dd), root(1, -1), up(1, -1), down(1, -1) {}
int create_x()
{
int res = data.size();
data.pb(0);
left.pb(-1);
right.pb(-1);
assert(res != -1);
return res;
}
int create_y()
{
int res = root.size();
root.pb(-1);
down.pb(-1);
up.pb(-1);
assert(res != -1);
return res;
}
void update_row(int l, int r, int index, int x, int val)
{
if (l + 1 == r)
{
data[index] += val;
return;
}
int m = l+r>>1;
if (m > x)
{
if (left[index] == -1)
{
int tmp = create_x();
left[index] = tmp;
}
assert(left[index] != -1);
update_row(l, m, left[index], x, val);
}
else
{
if (right[index] == -1)
{
int tmp = create_x();
right[index] = tmp;
}
assert(right[index] != -1);
update_row(m, r, right[index], x, val);
}
data[index] = 0;
if (left[index] != -1)
data[index] += data[left[index]];
if (right[index] != -1)
data[index] += data[right[index]];
}
void update_grid(int d, int u, int index, int x, int y, int val)
{
if (y >= u || d > y)
return;
if (root[index] == -1)
{
int tmp = create_x();
root[index] = tmp;
}
assert(root[index] != -1);
update_row(ll, rr, root[index], x, val);
if (d + 1 == u)
return;
int m = d+u>>1;
if (m > y)
{
if (down[index] == -1)
{
int tmp = create_y();
down[index] = tmp;;
}
assert(down[index] != -1);
update_grid(d, m, down[index], x, y, val);
}
else
{
if (up[index] == -1)
{
int tmp = create_y();
up[index] = tmp;
}
assert(up[index] != -1);
update_grid(m, u, up[index], x, y, val);
}
}
int get_row(int l, int r, int index, int xs, int xe)const
{
if (xs >= r || l >= xe || index == -1)
return 0;
if (xe >= r && l >= xs)
return data[index];
int m = l+r>>1;
int lres = get_row(l, m, left[index], xs, xe);
int rres = get_row(m, r, right[index], xs, xe);
return lres + rres;
}
int get_grid(int d, int u, int index, int xs, int xe, int ys, int ye)const
{
if (ys >= u || d >= ye || index == -1)
return 0;
if (ye >= u && d >= ys)
return get_row(ll, rr, root[index], xs, xe);
int m = d+u>>1;
int dres = get_grid(d, m, down[index], xs, xe, ys, ye);
int ures = get_grid(m, u, up[index], xs, xe, ys, ye);
return dres + ures;
}
void update(int x, int y, int val) { update_grid(dd, uu, 0, x, y, val); }
int get(int xs, int xe, int ys, int ye)const { return get_grid(dd, uu, 0, xs, xe, ys, ye); }
void clear()
{
for (int& i : data) i = 0;
}
};
const int BOTTOM_LEFT = 0;
const int TOP_LEFT = 2;
const int BOTTOM_RIGHT = BOTTOM_LEFT;
const int TOP_RIGHT = TOP_LEFT;
void solve2d()
{
int n, d, m;
cin >> n >> d >> m;
vector<array<int, 2>> v(n);
SegTree2d st[] = {SegTree2d(0, m, -2*m, 2*m), SegTree2d(0, m, -2*m, 2*m), SegTree2d(0, m, -2*m, 2*m), SegTree2d(0, m, -2*m, 2*m) } ;
for (auto& [x, y] : v)
{
cin >> x >> y;
x--, y--;
}
sort(v.begin(), v.end());
int64_t encounters = 0;
for (auto [x, y] : v)
{
encounters += st[BOTTOM_LEFT].get(0, y+1, -2*m+1, d-x-y+1);
encounters += st[TOP_LEFT].get(y+1, m, -2*m+1, d-x+y+1);
st[BOTTOM_LEFT].update(y, -x-y, 1);
st[TOP_LEFT].update(y, y-x, 1);
}
st[BOTTOM_LEFT].clear();
st[TOP_LEFT].clear();
for (int i = v.size()-1; i >= 0; i--)
{
auto [x, y] = v[i];
encounters += st[BOTTOM_RIGHT].get(0, y+1, -2*m+1, d+x-y+1);
encounters += st[TOP_RIGHT].get(y+1, m, -2*m+1, d+x+y+1);
st[BOTTOM_RIGHT].update(y, x-y, 1);
st[TOP_RIGHT].update(y, x+y, 1);
}
cout << (encounters / 2) << "\n";
}
int32_t main()
{
int b;
cin >> b;
if (b == 1)
solve1d();
else if (b == 2)
solve2d();
else
cout << "99\n";
}
Compilation message
pairs.cpp: In member function 'void SegTree1d::update(int, int, int, int, int)':
pairs.cpp:38:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m = l+r>>1;
| ~^~
pairs.cpp: In member function 'int SegTree1d::get(int, int, int, int, int)':
pairs.cpp:49:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m = l+r>>1;
| ~^~
pairs.cpp: In constructor 'SegTree2d::SegTree2d(int, int, int, int)':
pairs.cpp:86:27: warning: 'SegTree2d::up' will be initialized after [-Wreorder]
86 | vector<int> down, up;
| ^~
pairs.cpp:86:21: warning: 'std::vector<int> SegTree2d::down' [-Wreorder]
86 | vector<int> down, up;
| ^~~~
pairs.cpp:87:9: warning: when initialized here [-Wreorder]
87 | SegTree2d (int ll, int rr, int dd, int uu) : ll(ll), rr(rr), uu(uu), dd(dd), root(1, -1), up(1, -1), down(1, -1) {}
| ^~~~~~~~~
pairs.cpp: In member function 'void SegTree2d::update_row(int, int, int, int, int)':
pairs.cpp:113:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | int m = l+r>>1;
| ~^~
pairs.cpp: In member function 'void SegTree2d::update_grid(int, int, int, int, int, int)':
pairs.cpp:153:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
153 | int m = d+u>>1;
| ~^~
pairs.cpp: In member function 'int SegTree2d::get_row(int, int, int, int, int) const':
pairs.cpp:181:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
181 | int m = l+r>>1;
| ~^~
pairs.cpp: In member function 'int SegTree2d::get_grid(int, int, int, int, int, int, int) const':
pairs.cpp:192:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
192 | int m = d+u>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
948 KB |
Output is correct |
| 2 |
Correct |
30 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
23656 KB |
Output is correct |
| 2 |
Correct |
98 ms |
23616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
23604 KB |
Output is correct |
| 2 |
Correct |
90 ms |
5228 KB |
Output is correct |
| 3 |
Correct |
71 ms |
1756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
12612 KB |
Output is correct |
| 2 |
Correct |
27 ms |
12480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
3876 KB |
Output is correct |
| 2 |
Correct |
273 ms |
3804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1216 ms |
74004 KB |
Output is correct |
| 2 |
Correct |
1240 ms |
73968 KB |
Output is correct |
| 3 |
Correct |
845 ms |
35596 KB |
Output is correct |
| 4 |
Correct |
1122 ms |
59692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4082 ms |
490600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
