oj.uz

Submission #685265

# Submission time Handle Problem Language Result Execution time Memory
685265 2023-01-23T19:34:43 Z vjudge1 Pairs (IOI07_pairs) C++17
100 / 100
 285 ms 54896 KB 
#define taskname "rotate"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 1e5 + 10;
int n, d, m;
vector<int> fen[maxn];

void solve1()
{
    vector<int> v(n);
    for (int &x: v) cin>>x;
    sort(v.begin(), v.end());
    int ans = 0;
    for (int i=0; i<v.size(); i++)
    {
        int pos = upper_bound(v.begin(), v.end(), v[i] + d) - v.begin() - 1;
        ans += (pos - i);
    }
    cout<<ans;
}

inline void upd(int pos, int val) {for (; pos<=n; pos+=pos&-pos) fen[pos].emplace_back(val);}
inline int ask(int pos, int ub, int lb)
{
    int ans=0;
    for (; pos; pos-=pos&-pos)
        ans +=
            upper_bound(fen[pos].begin(), fen[pos].end(), ub) -
            lower_bound(fen[pos].begin(), fen[pos].end(), lb);
    return ans;
}
inline int qry(int l, int r, int ub, int lb) {if (l > r) return 0; return ask(r, ub, lb) - ask(l-1, ub, lb);}

void solve2()
{
    ii v[n+1];
    for (int i=1; i<=n; i++) cin>>v[i].ff>>v[i].ss, v[i] = {v[i].ff - v[i].ss, v[i].ff + v[i].ss};
    sort(v+1, v+n+1, [](ii x, ii y) {return x.ff < y.ff;});
    for (int i=1; i<=n; i++) upd(i, v[i].ss);
    for (int i=1; i<=n; i++) sort(fen[i].begin(), fen[i].end());
    int ans = 0;
    for (int i=1; i<=n; i++)
    {
        ii tmp = {v[i].ff + d + 1, 0};
        int pos = upper_bound(v+i+1, v+n+1, tmp) - v - 1;
        ans += qry(i+1, pos, v[i].ss + d, v[i].ss - d);
    }
    cout<<ans;
}

struct points {
    int f1, f2, f3, f4;
};
int bit[260][260][260];
inline void rupd(int x, int y, int z, int val)
{
    y += m, z += m;
    for (; x<=3*m; x+=x&-x)
        for (int yy=y; yy<=3*m; yy+=yy&-yy)
            for (int zz=z; zz<=3*m; zz+=zz&-zz)
                bit[x][yy][zz] += val;
}
inline int rqry(int x, int y, int z)
{
    int ans = 0;
    for (; x; x-=x&-x)
        for (int yy=y; yy; yy-=yy&-yy)
            for (int zz=z; zz; zz-=zz&-zz)
                ans += bit[x][yy][zz];
    return ans;
}
int qryr(int l1, int r1, int l2, int r2, int l3, int r3)
{
    l2 += m, r2 += m, l3 += m, r3 += m;
    l1 = max(l1, 1ll), l2 = max(l2, 1ll), l3 = max(l3, 1ll);
    r1 = min(r1, 3*m), r2 = min(r2, 3*m), r3 = min(r3, 3*m);
    return rqry(r1, r2, r3) - rqry(l1-1, r2, r3) - rqry(r1, l2-1, r3)
        - rqry(r1, r2, l3-1) + rqry(l1-1, l2-1, r3) + rqry(l1-1, r2, l3-1)
        + rqry(r1, l2-1, l3-1) - rqry(l1-1, l2-1, l3-1);
}
void solve3()
{
    points a[n+1];
    for (int i=1, x, y, z; i<=n; i++)
    {
        cin>>x>>y>>z;
        a[i] = {x-y-z, x+y+z, x-y+z, x+y-z};
    }
    int ans = 0;
    sort(a+1, a+n+1, [](points x, points y) {return x.f1 < y.f1;});
    for (int i=1, j=1; i<=n; i++)
    {
        while (j < i && a[i].f1 - a[j].f1 > d)
        {
            rupd(a[j].f2, a[j].f3, a[j].f4, -1);
            j++;
        }
        ans += qryr(a[i].f2-d, a[i].f2+d, a[i].f3-d, a[i].f3+d, a[i].f4-d, a[i].f4+d);
        rupd(a[i].f2, a[i].f3, a[i].f4, 1);
    }
    cout<<ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int b; cin>>b>>n>>d>>m;
    if (b == 1) solve1();
    else if (b == 2) solve2();
    else solve3();
}

Compilation message

pairs.cpp: In function 'void solve1()':
pairs.cpp:19:20: 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]
   19 |     for (int i=0; i<v.size(); i++)
      |                   ~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3796 KB Output is correct
2 Correct 14 ms 3844 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4228 KB Output is correct
2 Correct 19 ms 4228 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4228 KB Output is correct
2 Correct 19 ms 4308 KB Output is correct
3 Correct 19 ms 4228 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 13552 KB Output is correct
2 Correct 102 ms 13632 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 13800 KB Output is correct
2 Correct 189 ms 13760 KB Output is correct
3 Correct 166 ms 13804 KB Output is correct
4 Correct 176 ms 13760 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 14176 KB Output is correct
2 Correct 195 ms 14144 KB Output is correct
3 Correct 114 ms 14144 KB Output is correct
4 Correct 131 ms 14192 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19932 KB Output is correct
2 Correct 9 ms 19924 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7308 KB Output is correct
2 Correct 44 ms 7312 KB Output is correct
3 Correct 34 ms 7376 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 38024 KB Output is correct
2 Correct 187 ms 38128 KB Output is correct
3 Correct 63 ms 38124 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 54896 KB Output is correct
2 Correct 202 ms 54788 KB Output is correct
3 Correct 80 ms 54836 KB Output is correct