| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 708814 |
2023-03-12T11:30:05 Z |
cig32 |
Pairs (IOI07_pairs) |
C++17 |
|
2942 ms |
87576 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
#define int long long
using namespace __gnu_pbds;
typedef tree<pair<pair<int,int>,int>,null_type,less<pair<pair<int,int>,int> >,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
ordered_set bit[75010]; // 2D bit in regular matrices but only supporting single add/del
int id = 0;
map<pair<int, int>,vector<int> > mp;
int m;
void insert(int x, int y) {
id++;
mp[{y, x}].push_back(id);
for(;x<=m+2;x+=x&-x) bit[x].insert({{y, x}, id});
}
void erase(int x, int y) {
int ono = mp[{y, x}].back(); mp[{y, x}].pop_back();
for(;x<=m+2;x+=x&-x) bit[x].erase({{y, x}, ono});
}
int query(int x, int y) {
int sum = 0;
for(;x;x-=x&-x) sum += bit[x].order_of_key({{y+1, 0}, 0});
return sum;
}
bool cmp1(pair<int, int> x, pair<int, int> y) {
return x.first - x.second < y.first - y.second;
}
bool cmp2(pair<int, int> x, pair<int, int> y) {
return x.first + x.second < y.first + y.second;
}
bool cmp3(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
return x.first.first + x.first.second + x.second < y.first.first + y.first.second + y.second;
}
bool cmp4(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
return x.first.first + x.first.second - x.second < y.first.first + y.first.second - y.second;
}
bool cmp5(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
return x.first.first - x.first.second + x.second < y.first.first - y.first.second + y.second;
}
bool cmp6(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
return x.first.first - x.first.second - x.second < y.first.first - y.first.second - y.second;
}
const int bruh = 78;
int bit3[bruh][bruh][bruh];
void add(int x, int y, int z, int w) {
int X=x, Y=y, Z=z;
for(x=X;x<bruh;x+=x&-x) {
for(y=Y;y<bruh;y+=y&-y) {
for(z=Z;z<bruh;z+=z&-z) {
bit3[x][y][z] += w;
}
}
}
}
int sum(int x, int y, int z) {
int s=0;
int X=x, Y=y, Z=z;
for(x=X;x;x-=x&-x) {
for(y=Y;y;y-=y&-y) {
for(z=Z;z;z-=z&-z) {
s += bit3[x][y][z];
}
}
}
return s;
}
int solve1(vector<int> vt, int d) {
sort(vt.begin(), vt.end());
int ans = 0;
for(int j=0; j+1<vt.size(); j++) {
int lb = j+1, rb = vt.size() - 1;
while(lb < rb) {
int mid = (lb + rb + 1) >> 1;
if(vt[mid] - vt[j] <= d) lb = mid;
else rb = mid-1;
}
if(vt[lb] - vt[j] <= d) ans += (lb - j);
}
return ans;
}
int solve2(vector<pair<int,int> > vt, int d) {
mp.clear();
for(int i=0; i<=m+2; i++) bit[i].clear();
int n = vt.size();
int ans = 0;
pair<int, int> p[n+1];
for(int i=1; i<=n; i++) {
p[i] = vt[i-1];
}
sort(p+1, p+1+n, cmp1);
int j = 1;
for(int i=1; i<=n; i++) {
while(j < i && (p[i].first - p[i].second) - (p[j].first - p[j].second) > d) {
erase(p[j].first, m+1-p[j].second);
j++;
}
ans += query(p[i].first, m+1-p[i].second);
insert(p[i].first, m+1-p[i].second);
}
for(int i=j; i<=n; i++) erase(p[i].first, m+1-p[i].second);
j = 1;
sort(p+1, p+1+n, cmp2);
for(int i=1; i<=n; i++) {
while(j < i && (p[i].first + p[i].second) - (p[j].first + p[j].second) > d) {
erase(p[j].first, p[j].second);
j++;
}
ans += query(p[i].first, p[i].second);
insert(p[i].first, p[i].second);
}
vector<int> c[m+1];
for(int i=1; i<=n; i++) c[p[i].second].push_back(p[i].first);
for(int i=1; i<=m; i++) sort(c[i].begin(), c[i].end());
for(int i=1; i<=m; i++) {
ans -= solve1(c[i], d);
}
for(int i=1; i<=m; i++) c[i].clear();
for(int i=1; i<=n; i++) c[p[i].first].push_back(p[i].second);
for(int i=1; i<=m; i++) sort(c[i].begin(), c[i].end());
for(int i=1; i<=m; i++) {
ans -= solve1(c[i], d);
}
for(int i=1; i<=m; i++) c[i].clear();
map<pair<int,int>,int> mp;
for(int i=1; i<=n; i++) {
ans += mp[p[i]];
mp[p[i]]++;
}
return ans;
}
void solve(int tc) {
int b, n, d;
cin >> b >> n >> d >> m;
if(b == 2) {
vector<pair<int, int> > v;
for(int i=0; i<n; i++) {
int x, y;
cin >> x >> y;
v.push_back({x, y});
}
cout << solve2(v, d) << "\n"; return;
}
if(b == 1) {
vector<int> v;
for(int i=0; i<n; i++) {
int x;
cin >> x;
v.push_back(x);
}
cout << solve1(v, d) << "\n"; return;
}
if(b == 3) {
pair<pair<int,int>,int> p[n+1];
for(int i=1; i<=n; i++) {
cin >> p[i].first.first >> p[i].first.second >> p[i].second;
}
sort(p+1, p+1+n, cmp3);
int j = 1, ans = 0;
for(int i=1; i<=n; i++) {
while(j < i && (p[i].first.first + p[i].first.second + p[i].second) - (p[j].first.first + p[j].first.second + p[j].second) > d) {
add(p[j].first.first, p[j].first.second, p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, p[i].first.second, p[i].second);
add(p[i].first.first, p[i].first.second, p[i].second, 1);
}
for(int i=0; i<bruh; i++) for(int j=0; j<bruh; j++) for(int k=0; k<bruh; k++) bit3[i][j][k] = 0;
j = 1;
sort(p+1, p+1+n, cmp4);
for(int i=1; i<=n; i++) {
while(j < i && (p[i].first.first + p[i].first.second - p[i].second) - (p[j].first.first + p[j].first.second - p[j].second) > d) {
add(p[j].first.first, p[j].first.second, m+1-p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, p[i].first.second, m+1-p[i].second);
add(p[i].first.first, p[i].first.second, m+1-p[i].second, 1);
}
for(int i=0; i<bruh; i++) for(int j=0; j<bruh; j++) for(int k=0; k<bruh; k++) bit3[i][j][k] = 0;
j = 1;
sort(p+1, p+1+n, cmp5);
for(int i=1; i<=n; i++) {
while(j < i && (p[i].first.first - p[i].first.second + p[i].second) - (p[j].first.first - p[j].first.second + p[j].second) > d) {
add(p[j].first.first, m+1-p[j].first.second, p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, m+1-p[i].first.second, p[i].second);
add(p[i].first.first, m+1-p[i].first.second, p[i].second, 1);
}
for(int i=0; i<bruh; i++) for(int j=0; j<bruh; j++) for(int k=0; k<bruh; k++) bit3[i][j][k] = 0;
j = 1;
sort(p+1, p+1+n, cmp6);
for(int i=1; i<=n; i++) {
while(j < i && (p[i].first.first - p[i].first.second - p[i].second) - (p[j].first.first - p[j].first.second - p[j].second) > d) {
add(p[j].first.first, m+1-p[j].first.second, m+1-p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, m+1-p[i].first.second, m+1-p[i].second);
add(p[i].first.first, m+1-p[i].first.second, m+1-p[i].second, 1);
}
int t1=0, t2=0, t3=0;
for(int i=1; i<=m; i++) {
vector<pair<int,int> > vt;
for(int j=1; j<=n; j++) {
if(p[j].first.first == i) vt.push_back({p[j].first.second, p[j].second});
}
t1 += solve2(vt, d);
vt.clear();
for(int j=1; j<=n; j++) {
if(p[j].first.second == i) vt.push_back({p[j].first.first, p[j].second});
}
t1 += solve2(vt, d);
vt.clear();
for(int j=1; j<=n; j++) {
if(p[j].second == i) vt.push_back({p[j].first.first, p[j].first.second});
}
t1 += solve2(vt, d);
vt.clear();
}
vector<int> vv[m+1][m+1];
for(int i=1; i<=n; i++) vv[p[i].first.first][p[i].first.second].push_back(p[i].second);
for(int i=1; i<=m; i++) {
for(int j=1; j<=m; j++) {
t2 += solve1(vv[i][j], d);
}
}
for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) vv[i][j].clear();
for(int i=1; i<=n; i++) vv[p[i].first.first][p[i].second].push_back(p[i].first.second);
for(int i=1; i<=m; i++) {
for(int j=1; j<=m; j++) {
t2 += solve1(vv[i][j], d);
}
}
for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) vv[i][j].clear();
for(int i=1; i<=n; i++) vv[p[i].first.second][p[i].second].push_back(p[i].first.first);
for(int i=1; i<=m; i++) {
for(int j=1; j<=m; j++) {
t2 += solve1(vv[i][j], d);
}
}
for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) vv[i][j].clear();
map<pair<pair<int,int>,int>,int>wow;
for(int i=1; i<=n; i++) {
t3 += wow[p[i]];
wow[p[i]]++;
}
ans -= t1;
ans -= t2;
ans += t3 * 3;
cout << ans << "\n"; return;
cout << ans << " " << t1 << " " << t2 << " " << t3 << "\n";
int ck=0;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
ck += (abs(p[i].first.first-p[j].first.first) + abs(p[i].first.second-p[j].first.second) + abs(p[i].second-p[j].second) <= d);
}
}
cout << ck << "\n";
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
pairs.cpp: In function 'long long int solve1(std::vector<long long int>, long long int)':
pairs.cpp:92:19: 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]
92 | for(int j=0; j+1<vt.size(); j++) {
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
10548 KB |
Output is correct |
| 2 |
Correct |
21 ms |
10604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
10716 KB |
Output is correct |
| 2 |
Correct |
25 ms |
10732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
10684 KB |
Output is correct |
| 2 |
Correct |
30 ms |
10752 KB |
Output is correct |
| 3 |
Correct |
31 ms |
10648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10708 KB |
Output is correct |
| 2 |
Correct |
15 ms |
10700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
554 ms |
18708 KB |
Output is correct |
| 2 |
Correct |
702 ms |
45272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1183 ms |
42192 KB |
Output is correct |
| 2 |
Correct |
1758 ms |
55224 KB |
Output is correct |
| 3 |
Correct |
1208 ms |
50984 KB |
Output is correct |
| 4 |
Correct |
1368 ms |
48820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1979 ms |
46700 KB |
Output is correct |
| 2 |
Correct |
2942 ms |
73092 KB |
Output is correct |
| 3 |
Correct |
1519 ms |
87576 KB |
Output is correct |
| 4 |
Correct |
1834 ms |
64908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
12492 KB |
Output is correct |
| 2 |
Correct |
24 ms |
12464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
788 ms |
16956 KB |
Output is correct |
| 2 |
Correct |
842 ms |
18192 KB |
Output is correct |
| 3 |
Correct |
759 ms |
18820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1151 ms |
23032 KB |
Output is correct |
| 2 |
Correct |
1258 ms |
23564 KB |
Output is correct |
| 3 |
Correct |
1108 ms |
23804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1392 ms |
24748 KB |
Output is correct |
| 2 |
Correct |
1410 ms |
25280 KB |
Output is correct |
| 3 |
Correct |
1267 ms |
25552 KB |
Output is correct |
