Submission #1273235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273235		KasymK	Pairs (IOI07_pairs)	C++17	100 / 100	241 ms	25004 KiB

pairs

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second    
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int mxN=1e5;
int b, n, d, m;
ll answer=0;

namespace subtask2 {
    static const int MG1=1.5e5;
    array<int, 2> a[mxN];
    int f[MG1];
    void upd(int x, int vl){
        x++;
        for(; x < MG1; x+=x&-x)
            f[x]+=vl;
    }

    int qry(int x){
        int ret=0;
        for(; x >= 1; x-=x&-x)
            ret+=f[x];
        return ret;
    }
    void solve() {
        for(int i=0; i<n; ++i){
            scanf("%d", &a[i][0]);
            if(b^1) {
                scanf("%d", &a[i][1]);
                tie(a[i][0], a[i][1])=make_pair(a[i][0]+a[i][1], a[i][0]-a[i][1]-1+m);
            }
        }
        sort(a, a+n);
        for(int i=0, j=0; i<n; ++i){
            while(a[j][0]<a[i][0]-d)
                upd(a[j++][1], -1);
            answer+=qry(min(a[i][1]+d+1, MG1-1))-qry(max(a[i][1]-d, 0));
            upd(a[i][1], 1);
        }
    }
}

namespace subtask3 {
    static const int MG1=223;
    array<int, 3> a[mxN];
    array<int, 4> b[mxN];
    int f[MG1+1][MG1+1][MG1+1];

    void upd(int x, int y, int z){
        for(int j1=x+1; j1<=MG1; j1+=j1&-j1)
            for(int j2=y+1; j2<=MG1; j2+=j2&-j2)
                for(int j3=z+1; j3<=MG1; j3+=j3&-j3)
                    f[j1][j2][j3]++;
    }
    int qry(int x, int y, int z){
        int ret=0;
        for(int j1=x; j1; j1-=j1&-j1)
            for(int j2=y; j2; j2-=j2&-j2)
                for(int j3=z; j3; j3-=j3&-j3)
                    ret+=f[j1][j2][j3];
        return ret;
    }
    void solve() {
        for(int i=0; i<n; ++i){
            for(int ad = 0; ad < 3; ++ad)
                scanf("%d", &a[i][ad]);
            b[i][0]=a[i][0]+a[i][1]+a[i][2]-3;
            b[i][1]=a[i][0]+a[i][1]-a[i][2]-2+m;
            b[i][2]=a[i][0]-a[i][1]+a[i][2]-2+m;
            b[i][3]=a[i][0]-a[i][1]-a[i][2]-1+2*m;
        }
        for(int i=0; i<MG1; ++i){
            for(int j=0; j<n; ++j)
                if(b[j][3]==i)
                    upd(b[j][0], b[j][1], b[j][2]);
            for(int j=0; j<n; ++j){
                if(i^b[j][3]-d-1 and i^min(b[j][3]+d, MG1-1))
                    continue;
                int l1=max(b[j][0]-d, 0), r1=min(b[j][0]+d+1, MG1), l2=max(b[j][1]-d, 0), r2=min(b[j][1]+d+1, MG1), l3=max(b[j][2]-d, 0), r3=min(b[j][2]+d+1, MG1);
                answer+=(i^b[j][3]-d-1?1:-1)*(qry(r1, r2, r3)-qry(r1, r2, l3)-qry(r1, l2, r3)+qry(r1, l2, l3)-qry(l1, r2, r3)+qry(l1, r2, l3)+qry(l1, l2, r3)-qry(l1, l2, l3));
            }
        }
        answer=(answer-n)/2;
    }
}

int main(){
    scanf("%d%d%d%d", &b, &n, &d, &m);
    if(b<3)
        subtask2::solve();
    else
        subtask3::solve();
    printf("%lld\n", answer);
}

Compilation message (stderr)

pairs.cpp: In function 'void subtask2::solve()':
pairs.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |             scanf("%d", &a[i][0]);
      |             ~~~~~^~~~~~~~~~~~~~~~
pairs.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |                 scanf("%d", &a[i][1]);
      |                 ~~~~~^~~~~~~~~~~~~~~~
pairs.cpp: In function 'void subtask3::solve()':
pairs.cpp:76:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |                 scanf("%d", &a[i][ad]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d%d%d%d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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