oj.uz

답안 #333241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333241 2020-12-05T04:12:25 Z CodeTiger927 Pairs (IOI07_pairs) C++14
72 / 100
 4000 ms 524292 KB 
using namespace std;

#include <iostream>

int B,D,N,M;

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

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

int main() {
	scanf("%d %d %d %d",&B,&N,&D,&M);
	long long ans = 0;
	if(B == 1) {
		node1d* st = new node1d();
		for(int i = 0;i < N;++i) {
			int a;
			scanf("%d",&a);
			ans += st -> qry(0,M,max(0,a - D),a + D);
			st -> upd(0,M,a,1);
		}
	}else if(B == 2) {
		node2d* st = new node2d();
		for(int i = 0;i < N;++i) {
			int c,d;
			scanf("%d %d",&c,&d);
			int a = (c + d);
			int b = (c - d) + M;
			ans += st -> qry(0,2 * M,max(0,a - D),a + D,max(0,b - D),b + D);
			st -> upd(0,2 * M,a,b,1);
		}
	}else{
		node2d* st[80];
		for(int i = 0;i <= M;++i) {
			st[i] = new node2d();
		}
		for(int i = 0;i < N;++i) {
			int d,e,f;
			scanf("%d %d %d",&d,&e,&f);
			int a = (d + e);
			int b = (d - e) + M;
			int c = f;
			// cout << a << " " << b << " " << c << endl;
			for(int j = 0;j <= M;++j) {
				int curD = D - abs(c - j);
				if(curD < 0) continue;
				ans += st[j] -> qry(0,2 * M,max(0,a - curD),a + curD,max(0,b - curD),b + curD);
			}
			st[c] -> upd(0,2 * M,a,b,1);
		}
		
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |  scanf("%d %d %d %d",&B,&N,&D,&M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |    scanf("%d",&a);
      |    ~~~~~^~~~~~~~~
pairs.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |    scanf("%d %d",&c,&d);
      |    ~~~~~^~~~~~~~~~~~~~~
pairs.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |    scanf("%d %d %d",&d,&e,&f);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 876 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 364 KB Output is correct
2 Correct 23 ms 364 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 33516 KB Output is correct
2 Correct 107 ms 33516 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 33516 KB Output is correct
2 Correct 95 ms 6636 KB Output is correct
3 Correct 53 ms 1516 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 9068 KB Output is correct
2 Correct 17 ms 9068 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 2668 KB Output is correct
2 Correct 86 ms 2668 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1077 ms 67308 KB Output is correct
2 Correct 866 ms 67180 KB Output is correct
3 Correct 656 ms 34796 KB Output is correct
4 Correct 672 ms 53520 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2840 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2156 KB Output is correct
2 Correct 4 ms 2156 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 620 KB Output is correct
2 Correct 256 ms 624 KB Output is correct
3 Correct 49 ms 620 KB Output is correct

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3138 ms 32952 KB Output is correct
2 Execution timed out 4081 ms 23020 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4021 ms 32580 KB Time limit exceeded
2 Halted 0 ms 0 KB -