제출 #119705

#제출 시각아이디문제언어결과실행 시간메모리
119705eriksuenderhaufPairs (IOI07_pairs)C++11
100 / 100
180 ms10104 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define piii pair<pii,int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second #define X fi.fi #define Y fi.se #define Z se using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAX2 = 263000 + 5; const int MAX3 = 80 + 5; const double eps = 1e-9; int b, n, d, m; int BIT2[MAX2], sm3[MAX3][2*MAX3][2*MAX3]; void upd2(int ind, int v) { ind++; while (ind < MAX2) { BIT2[ind] += v; ind += ind & -ind; } } int qry2(int ind) { ind++; int ret = 0; while (ind > 0) { ret += BIT2[ind]; ind -= ind & -ind; } return ret; } ll qry2(int l, int r) { return qry2(r) - qry2(l - 1); } ll calc(int xL, int xH, int yL, int yH, int z) { tie(xL, xH) = mp(max(1, xL), min(2*m, xH)); tie(yL, yH) = mp(max(1, yL), min(2*m, yH)); return sm3[z][xH][yH] - sm3[z][xH][yL-1] - sm3[z][xL-1][yH] + sm3[z][xL-1][yL-1]; } int main() { scanf("%d %d %d %d", &b, &n, &d, &m); ll ans = 0; if (b == 1) { vector<int> a; a.resize(n); for (int i = 0; i < n; i++) ni(a[i]); sort(a.begin(), a.end()); int j = 0; for (int i = 0; i < n; i++) { while (j <= i && a[i]-a[j] > d) j++; ans += (ll) (i - j); } } else if (b == 2) { vector<pii> a; a.resize(n); for (int i = 0; i < n; i++) { scanf("%d %d", &a[i].fi, &a[i].se); a[i] = mp(a[i].fi-a[i].se, a[i].fi+a[i].se); } sort(a.begin(), a.end()); int j = 0; for (int i = 0; i < n; i++) { while (j <= i && a[i].fi-a[j].fi > d) upd2(a[j++].se, -1); ans += qry2(a[i].se - d, a[i].se + d); upd2(a[i].se, 1); } } else { vector<piii> a; a.resize(n); for (int i = 0; i < n; i++) { scanf("%d %d %d", &a[i].X, &a[i].Y, &a[i].Z); sm3[a[i].Z][a[i].X+a[i].Y-1][a[i].X-a[i].Y+m]++; } for (int i = 1; i <= m; i++) for (int j = 1; j <= 2*m; j++) for (int k = 1; k <= 2*m; k++) sm3[i][j][k] += sm3[i][j-1][k] + sm3[i][j][k-1] - sm3[i][j-1][k-1]; for (int i = 0; i < n; i++) { int v1 = a[i].X+a[i].Y-1, v2 = a[i].X-a[i].Y+m, v3 = a[i].Z; ans += calc(v1-d, v1+d, v2-d, v2+d, v3) - 1; for (int j = 1; j <= min(d, m); j++) { if (v3 - j >= 0) ans += calc(v1-(d-j), v1+(d-j), v2-(d-j), v2+(d-j), v3-j); if (v3 + j <= m) ans += calc(v1-(d-j), v1+(d-j), v2-(d-j), v2+(d-j), v3+j); } } ans /= 2ll; } prl(ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

pairs.cpp: In function 'int main()':
pairs.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &b, &n, &d, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
pairs.cpp:80:4: note: in expansion of macro 'ni'
    ni(a[i]);
    ^~
pairs.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &a[i].fi, &a[i].se);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &a[i].X, &a[i].Y, &a[i].Z);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...