oj.uz

답안 #77356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77356 2018-09-26T05:13:23 Z shoemakerjo 팀들 (IOI15_teams) C++14
0 / 100
 1555 ms 525312 KB 
#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

#define maxn 500010
vector<pii> stuff;
int n;

struct node {

	int ct;
	node *left; node *right;

	node (node *ll, node *rr, int cc) : 
		left(ll), right(rr), ct(cc) {}

	node * update(int lo, int hi, int spot, int diff);

};


node *roots[maxn];
vector<vector<int>> badds(maxn);
vector<vector<int>> bsubs(maxn);


node *null = new node(NULL, NULL, 0);

node * node :: update(int lo, int hi, int spot, int diff) {
	if (lo == hi) return new node(null, null, this->ct + diff);
	int mid = (lo + hi)/2;
	if (spot <= mid) {
		return new node(this->left->update(lo, mid, spot, diff),
		this->right,  this->ct+diff);
	}
	return new node(this->left, this->right->update(mid+1, hi, spot, diff),
		 this->ct+diff);
}

void init(int N, int A[], int B[]) {
	// cout << "here" << endl;
	null->left = null;
	null->right = null;
	n = N;
	for (int i = 0; i < n; i++) {
		stuff.push_back(pii(B[i], A[i]));
	}
	sort(stuff.begin(), stuff.end());
	for (int i = 0; i < n; i++) {
		badds[stuff[i].second].push_back(i+1);
		bsubs[stuff[i].first+1].push_back(i+1);
	}
	roots[0] = null;
	for (int i = 1; i <= n; i++) {
		roots[i] = roots[i-1];
		for (int vv : badds[i]) roots[i] = roots[i]->update(1, n+1, vv, 1);
		for (int vv : bsubs[i]) roots[i] = roots[i]->update(1, n+1, vv, -1);

	}

}

node * remo(node * cur, int ss, int se, int qs, int qe) {
	if (qs > qe || ss > se || qs > se || qe < ss) return cur;
	if (qs <= ss && se <= qe) return null;
	int mid = (ss+se)/2;
	node *ll = remo(cur->left, ss, mid, qs, qe);
	node *rr = remo(cur->right, mid+1, se, qs, qe);
	return new node (ll, rr, ll->ct + rr->ct);
}

node * godown(node *used, node *active, int k, int ss, int se) {
	// cout << "   " << used->ct << " " << active ->ct << " " << k  << endl;
	assert(active ->ct - used ->ct >= k);
	assert(ss <= se);

	int lsub = active->left->ct - used->left->ct;
	int mid = (ss+se)/2;

	if (ss == se) {
		if (k == 0) {
			return used;
		}
		return active;
	}

	if (lsub >= k) {
	
		node *ll = godown(used->left, active->left, k, ss, mid);
		node *rr = active->right;
		return new node (ll, rr, ll->ct + rr->ct);
	}

	node *ll = active->left;
	node *rr = godown(used->right, active->right, k - lsub, mid+1, se);
	return new node(ll, rr, ll->ct + rr->ct);

}

int can(int M, int K[]) {
	int lspot = 1;
	vector<int> vals;
	for (int i = 0; i < M; i++) {
		vals.push_back(K[i]);
	}
	sort(vals.begin(), vals.end());
	node * used = null;
	for (int vv : vals) {
		// cout << "going for " << vv << endl;
		used = remo(used, 1, n+1, 1, vv-1); 
		// cout << "   done removing" << endl;
		if (roots[vv]->ct - used->ct < vv) {
			// cout << "QUERY FAILED" << endl;
			return 0;
			// cout << "QUERY FAILED" << endl;
		}
		used = godown(used, roots[vv], vv, 1, n+1);
		//remove all b's less than the val that I have taken
	}
	// cout << "QUERY SUCCEEDED" << endl;
	return 1;

}

Compilation message

teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:15:20: warning: 'node::right' will be initialized after [-Wreorder]
  node *left; node *right;
                    ^~~~~
teams.cpp:14:6: warning:   'int node::ct' [-Wreorder]
  int ct;
      ^~
teams.cpp:17:2: warning:   when initialized here [-Wreorder]
  node (node *ll, node *rr, int cc) : 
  ^~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:104:6: warning: unused variable 'lspot' [-Wunused-variable]
  int lspot = 1;
      ^~~~~

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 23988 KB Output is correct
2 Correct 23 ms 24084 KB Output is correct
3 Correct 25 ms 24152 KB Output is correct
4 Correct 24 ms 24172 KB Output is correct
5 Correct 23 ms 24224 KB Output is correct
6 Correct 23 ms 24356 KB Output is correct
7 Incorrect 24 ms 24424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 142160 KB Output is correct
2 Correct 345 ms 143256 KB Output is correct
3 Correct 345 ms 144612 KB Output is correct
4 Correct 345 ms 147088 KB Output is correct
5 Incorrect 246 ms 147088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 149048 KB Output is correct
2 Correct 352 ms 150648 KB Output is correct
3 Correct 614 ms 230416 KB Output is correct
4 Correct 355 ms 230416 KB Output is correct
5 Incorrect 251 ms 230416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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