oj.uz

Submission #330644

# Submission time Handle Problem Language Result Execution time Memory
330644 2020-11-26T03:41:42 Z gmyu Pairs (IOI07_pairs) C++14
100 / 100
 467 ms 41708 KB 
/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e6+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE2 {
    int x, y;

    bool operator< (NODE2 b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct NODE4 {
    int x, y, z, t;

    bool operator< (NODE4 b) const {
        if(x != b.x) return x < b.x;
        if(y != b.y) return y < b.y;
        if(z != b.z) return z < b.z;
        return t < b.t;
    }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

int B, N, D, M;
int x[MAXV];
NODE2 p2[MAXV];
NODE4 p4[MAXV];


/// Binary Index Tree for fast presum calculation with updates O(N logN)
#define MAXBIT1 200007
template<class T, int SZ> struct BIT1 {
	T bit[SZ+1];
	/// add one item and updated prefix sum of an array, O(N logN)
	void upd(int pos, T x) {
		for (; pos <= SZ; pos += (pos&-pos))
            bit[pos] += x;
	}
	/// get prefix sum of an array at position idx, 0(N log N)
	/// index starts from 1
	T getSum(int r) {
		T res = 0;
		for (; r; r -= (r&-r))
			res += bit[r];
		return res;
	}
	/// get sum between (l, r) all inclusive
	T rangeSum(int l, int r) {
		return getSum(r) - getSum(l-1);
	}
};

/// Binary Index Tree for fast presum calculation with updates O(N logN)
/// https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
/// 2D BIT: https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/
#define MAXBIT3 400
template<class T, int SZ> struct BIT3 {
	T bit[SZ+1][SZ+1][SZ+1];

	void init(){
	    for(int y = 0; y <= SZ; y++)
            for(int z = 0; z <= SZ; z++)
                for(int t = 0; t <= SZ; t++)
                    bit[y][z][t] = 0;
	}
	/// add one item and updated prefix sum of an array, O(N logN)
	void upd(int pos_y, int pos_z, int pos_t, T val) {
		int y, z, t;
		for (y = pos_y; y <= SZ; y += (y&-y)) {
            for (z = pos_z; z <= SZ; z += (z&-z))
                for (t = pos_t; t <= SZ; t += (t&-t))
                    bit[y][z][t] += val;
		}
	}
	/// get prefix sum of an array at position idx, 0(N log N)
	/// index starts from 1
	T getSum(int pos_y, int pos_z, int pos_t) {
		T res = 0;
		int y, z, t;
		for (y = pos_y; y > 0; y -= (y&-y)) {
            for (z = pos_z; z > 0; z -= (z&-z))
                for (t = pos_t; t > 0; t -= (t&-t))
                    res += bit[y][z][t];
		}
		return res;
	}
	/// get sum between (x1, y1) - (x2, y2) all inclusive
	T rangeSum(int y1, int z1, int t1, int y2, int z2, int t2) {
		return getSum(y2, z2, t2) - getSum(y1-1, z2, t2) - getSum(y2, z1-1, t2) - getSum(y2, z2, t1-1)
            + getSum(y1-1, z1-1, t2) + getSum(y1-1, z2, t1-1) + getSum(y2, z1-1, t1-1) - getSum(y1-1, z1-1, t1-1);
	}

};

int main() {
    debug = false; submit = false;
    if(submit) setIO("testName");

    int i, j, k;
    ll ans = 0LL;

    cin >> B >> N >> D >> M;

    if(B == 1) {
        for(i=1; i<= N; i++) cin >> x[i];
        sort(x+1, x+N+1);

        int le = 1;
        int s = 0;;
        for(i = 1; i<=N; i++) {
            while(x[i] - x[le] > D) {
                s--; le++;
            }
            ans += (ll)s;
            //if(debug) cout << i << " " << x[i] << " " << le << " " << s << " " << ans << endl;
            s++;
        }
    }

    if(B == 2) {
        int x0, y0;
        int minx = MX, miny = MX;
        for(i=1; i <=N; i++) {
            cin >> x0 >> y0;
            p2[i].x = y0 + x0; p2[i].y = y0 - x0;
            minx = min(minx, p2[i].x); miny = min(miny, p2[i].y);
        }
        for(i=1; i <=N; i++) {
            p2[i].x -= (minx -1); p2[i].y -= (miny -1);
        }
        sort(p2+1, p2+1+N);

        int le = 1;
        BIT1<ll, MAXBIT1> myBit1;

        for(i=1; i<=N; i++) {
            while(p2[i].x - p2[le].x > D) {
                myBit1.upd(p2[le].y, -1);
                le++;
            }
            ans += (ll)myBit1.rangeSum(max(1, p2[i].y - D), min(MAXBIT1, p2[i].y + D));
            myBit1.upd(p2[i].y, 1);
        }
    }

    if(B == 3) {
        int x0, y0, z0;
        int minx = MX, miny = MX, minz = MX, mint = MX;
        for(i=1; i<=N; i++) {
            cin >> x0 >> y0 >> z0;
            p4[i].x = z0 + (y0+x0); p4[i].y = z0 - (y0+x0); p4[i].z = z0 + (y0-x0); p4[i].t = z0 - (y0-x0);
            minx = min(minx, p4[i].x); miny = min(miny, p4[i].y); minz = min(minz, p4[i].z); mint = min(mint, p4[i].t);
        }

        int mr = -1;
        for(i=1; i<=N; i++) {
            p4[i].x -= (minx -1); p4[i].y -= (miny -1); p4[i].z -= (minz -1); p4[i].t -= (mint -1);
            mr = max(mr, p4[i].y); mr = max(mr, p4[i].z); mr = max(mr, p4[i].t);
        }
        sort(p4+1, p4+1+N);

        int le = 1;
        BIT3<int, MAXBIT3> myBit3;

        for(i=1; i<=N; i++) {
            while(p4[i].x - p4[le].x > D) {
                myBit3.upd(p4[le].y, p4[le].z, p4[le].t, -1);
                le++;
            }
            ans += (ll)myBit3.rangeSum(max(1, p4[i].y-D), max(1, p4[i].z-D), max(1, p4[i].t-D),
                                       min(MAXBIT3, p4[i].y+D), min(MAXBIT3, p4[i].z+D), min(MAXBIT3, p4[i].t+D));
            myBit3.upd(p4[i].y, p4[i].z, p4[i].t, 1);
        }
    }

    cout << ans << endl;

}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:137:12: warning: unused variable 'j' [-Wunused-variable]
  137 |     int i, j, k;
      |            ^
pairs.cpp:137:15: warning: unused variable 'k' [-Wunused-variable]
  137 |     int i, j, k;
      |               ^
pairs.cpp: In function 'void setIO(std::string)':
pairs.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 748 KB Output is correct
2 Correct 28 ms 748 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 748 KB Output is correct
2 Correct 60 ms 684 KB Output is correct
3 Correct 50 ms 748 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1132 KB Output is correct
2 Correct 53 ms 1292 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1132 KB Output is correct
2 Correct 63 ms 1132 KB Output is correct
3 Correct 69 ms 1132 KB Output is correct
4 Correct 67 ms 1132 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 2284 KB Output is correct
2 Correct 76 ms 2284 KB Output is correct
3 Correct 76 ms 2156 KB Output is correct
4 Correct 93 ms 2156 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18156 KB Output is correct
2 Correct 13 ms 18284 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3652 KB Output is correct
2 Correct 184 ms 3564 KB Output is correct
3 Correct 119 ms 3564 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 28908 KB Output is correct
2 Correct 340 ms 28908 KB Output is correct
3 Correct 159 ms 28908 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 41708 KB Output is correct
2 Correct 361 ms 41580 KB Output is correct
3 Correct 202 ms 41580 KB Output is correct