| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 708802 |
2023-03-12T10:29:53 Z |
cig32 |
Pairs (IOI07_pairs) |
C++17 |
|
2978 ms |
88204 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) {
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, 76-p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, p[i].first.second, 76-p[i].second);
add(p[i].first.first, p[i].first.second, 76-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, 76-p[j].first.second, p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, 76-p[i].first.second, p[i].second);
add(p[i].first.first, 76-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, 76-p[j].first.second, 76-p[j].second, -1);
j++;
}
ans += sum(p[i].first.first, 76-p[i].first.second, 76-p[i].second);
add(p[i].first.first, 76-p[i].first.second, 76-p[i].second, 1);
}
cout << ans << "\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 |
8548 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
21 ms |
10596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
11036 KB |
Output is correct |
| 2 |
Correct |
26 ms |
11080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
11224 KB |
Output is correct |
| 2 |
Correct |
40 ms |
11092 KB |
Output is correct |
| 3 |
Correct |
37 ms |
11028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10708 KB |
Output is correct |
| 2 |
Correct |
14 ms |
10708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
610 ms |
18772 KB |
Output is correct |
| 2 |
Correct |
729 ms |
45380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1265 ms |
42492 KB |
Output is correct |
| 2 |
Correct |
1907 ms |
55440 KB |
Output is correct |
| 3 |
Correct |
1403 ms |
51264 KB |
Output is correct |
| 4 |
Correct |
1503 ms |
48960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2063 ms |
47300 KB |
Output is correct |
| 2 |
Correct |
2978 ms |
73596 KB |
Output is correct |
| 3 |
Correct |
1534 ms |
88204 KB |
Output is correct |
| 4 |
Correct |
1851 ms |
65420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
15140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
15544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
15464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
