oj.uz

답안 #347671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347671 2021-01-13T10:16:12 Z Markomafko972 Meteors (POI11_met) C++14
24 / 100
 6000 ms 65540 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, a, q;
vector<int> v[300005];
pair< pii, int > w[300005];
ll loga[300005];

void update(int x, int y) {
	x++;
	for (; x <= 300000; x += x & -x) loga[x] += y;
}

ll query(int x) {
	x++;
	ll out = 0;
	for (; x > 0; x -= x & -x) out += loga[x];
	return out;
}

vector< pair<pii, int> > gdje[300005];
vector< pair<pii, int> > slj[300005];
int sol[300005];
int treba[300005];

int main () {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a;
		v[a-1].push_back(i);
	}
	
	for (int i = 0; i < n; i++) cin >> treba[i];
	
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> w[i].X.X >> w[i].X.Y >> w[i].Y;
		w[i].X.X --;
		w[i].X.Y --;
	}
	
	/*for (int i = 0; i < q; i++) {
		if (w[i].X.X <= w[i].X.Y) {
			update(w[i].X.X, w[i].Y);
			update(w[i].X.Y+1, -w[i].Y);
		}
		else {
			update(w[i].X.X, w[i].Y);	
			update(0, w[i].Y);
			update(w[i].X.Y+1, -w[i].Y);
		}
	}*/
	
	int kol = n;
	for (int i = 0; i < n; i++) {
		gdje[(q-1)/2].push_back({{0, q-1}, i});
	}
	
	memset(sol, -1, sizeof sol);
	int br = 0;
	while (kol > 0) {
		for (int i = 0; i < q; i++) {
			if (w[i].X.X <= w[i].X.Y) {
				update(w[i].X.X, w[i].Y);
				update(w[i].X.Y+1, -w[i].Y);
			}
			else {
				update(w[i].X.X, w[i].Y);
				update(0, w[i].Y);
				update(w[i].X.Y+1, -w[i].Y);
			}
			
			/*cout << "QUERY" << endl;
			for (int j = 0; j < m; j++) cout << query(j) << " ";
			cout << endl; */
			
			for (int j = 0; j < gdje[i].size(); j++) {
				unsigned long long zbr = 0;
				for (int k = 0; k < v[gdje[i][j].Y].size(); k++) {
					//cout << "dodaj poziciju " << v[gdje[i][j].Y][k] << endl;
					zbr += query(v[gdje[i][j].Y][k]);
					if (zbr >= treba[gdje[i][j].Y]) break;
				}
				
				//cout << gdje[i][j].X.X << " do " << gdje[i][j].X.Y << ": " << gdje[i][j].Y << " " << zbr << endl;
				//system("pause");
				
				if (gdje[i][j].X.X == gdje[i][j].X.Y) {
					if (zbr >= treba[gdje[i][j].Y]) sol[gdje[i][j].Y] = i+1;
					else sol[gdje[i][j].Y] = -1;
					
					kol--;
				}
				else {
					if (zbr < treba[gdje[i][j].Y] && (i+1+gdje[i][j].X.Y)/2 >= 0 && (i+1+gdje[i][j].X.Y)/2 < q) slj[(i+1+gdje[i][j].X.Y)/2].push_back({{i+1, gdje[i][j].X.Y}, gdje[i][j].Y});
					else if ((gdje[i][j].X.X+i)/2 >= 0 && (gdje[i][j].X.X+i)/2 < q) {
						slj[(gdje[i][j].X.X+i)/2].push_back({{gdje[i][j].X.X, i}, gdje[i][j].Y});
					}
				}
			}
		}
		
		for (int i = 0; i < q; i++) {
			gdje[i] = slj[i];
			slj[i].clear();
		}
		
		memset(loga, 0, sizeof loga);
		
		br++;
		if (br == 15) {
			while (1) {
				
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		if (sol[i] == -1) cout << "NIE\n";
		else cout << sol[i] << "\n";
	}

	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for (int j = 0; j < gdje[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~
met.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int k = 0; k < v[gdje[i][j].Y].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:92:14: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   92 |      if (zbr >= treba[gdje[i][j].Y]) break;
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~
met.cpp:99:14: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   99 |      if (zbr >= treba[gdje[i][j].Y]) sol[gdje[i][j].Y] = i+1;
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~
met.cpp:105:14: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
  105 |      if (zbr < treba[gdje[i][j].Y] && (i+1+gdje[i][j].X.Y)/2 >= 0 && (i+1+gdje[i][j].X.Y)/2 < q) slj[(i+1+gdje[i][j].X.Y)/2].push_back({{i+1, gdje[i][j].X.Y}, gdje[i][j].Y});
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25068 KB Output is correct
2 Correct 21 ms 25196 KB Output is correct
3 Correct 20 ms 25068 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25068 KB Output is correct
2 Correct 23 ms 25068 KB Output is correct
3 Correct 22 ms 25324 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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