Submission #685265

#	Time	Username	Problem	Language	Result	Execution time	Memory
685265		vjudge1	Pairs (IOI07_pairs)	C++17	100 / 100	285 ms	54896 KiB

pairs

#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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10