oj.uz

Submission #333233

# Submission time Handle Problem Language Result Execution time Memory
333233 2020-12-05T04:00:30 Z CodeTiger927 Pairs (IOI07_pairs) C++14
52 / 100
 1913 ms 524288 KB 
using namespace std;

#include <iostream>

int B,D,N,M;

struct node1d {
    int l,r,v;
    node1d *c[2];
    node1d(int l,int r) : l{l}, r{r} {
        v = 0;
        c[0] = nullptr;
        c[1] = nullptr;
    } 
    void upd(int x,int v) {
        this -> v += v;
        if(l != r) {
            int m = (l + r) >> 1;
            if(x <= m) {
                if(!c[0]) c[0] = new node1d(l,m);
                c[0] -> upd(x,v);
            }else{
                if(!c[1]) c[1] = new node1d(m + 1,r);
                c[1] -> upd(x,v);
            }
        }
    }
    int qry(int x,int y) {
        if(x <= l && r <= y) return v;
        if(y < l || x > r) return 0;
        int res = 0;
        if(c[0]) res += c[0] -> qry(x,y);
        if(c[1]) res += c[1] -> qry(x,y);
        return res;
    }
};

struct node2d {
    int l,r;
    node1d* v;
    node2d *c[2];
    node2d(int l,int r) : l{l}, r{r} {
        if(B == 3) {
        	v = new node1d(0,160);
        }else{
      		v = new node1d(0,160000);
        }
        c[0] = nullptr;
        c[1] = nullptr;
    } 
    void upd(int x,int y,int v) {
        this -> v -> upd(y,v);
        if(l != r) {
            int m = (l + r) >> 1;
            if(x <= m) {
                if(!c[0]) c[0] = new node2d(l,m);
                c[0] -> upd(x,y,v);
            }else{
                if(!c[1]) c[1] = new node2d(m + 1,r);
                c[1] -> upd(x,y,v);
            }
        }
    }
    int qry(int x1,int x2,int y1,int y2) {
        if(x1 <= l && r <= x2) return v -> qry(y1,y2);
        if(x2 < l || x1 > r) return 0;
        int res = 0;
        if(c[0]) res += c[0] -> qry(x1,x2,y1,y2);
        if(c[1]) res += c[1] -> qry(x1,x2,y1,y2);
        return res;
    }
};

int main() {
	cin >> B >> N >> D >> M;
	long long ans = 0;
	if(B == 1) {
		node1d* st = new node1d(0,75000005);
		for(int i = 0;i < N;++i) {
			int a;
			cin >> a;
			ans += st -> qry(max(0,a - D),a + D);
			st -> upd(a,1);
		}
	}else if(B == 2) {
		node2d* st = new node2d(0,160000);
		for(int i = 0;i < N;++i) {
			int c,d;
			cin >> c >> d;
			int a = (c + d);
			int b = (c - d) + 80000;
			ans += st -> qry(max(0,a - D),a + D,max(0,b - D),b + D);
			st -> upd(a,b,1);
		}
	}else{

		
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 1132 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 51092 KB Output is correct
2 Correct 163 ms 51052 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 51052 KB Output is correct
2 Correct 157 ms 10604 KB Output is correct
3 Correct 95 ms 2924 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 4972 KB Output is correct
2 Correct 287 ms 5100 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1706 ms 106604 KB Output is correct
2 Correct 1461 ms 106476 KB Output is correct
3 Correct 1125 ms 55916 KB Output is correct
4 Correct 1166 ms 85612 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1913 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -