| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 347740 |
2021-01-13T10:51:51 Z |
Lukap |
Meteors (POI11_met) |
C++14 |
|
6000 ms |
26456 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3 * 1e5 + 7;
const int OFF = (1<<19);
int n,m,k;
int pripadnost[MAXN],zadvoljstvo[MAXN];
int l[MAXN],r[MAXN],xi[MAXN];
vector<int> sektori[MAXN];
long long zbroj[MAXN];
long long tour[2 * OFF];
long long middle[MAXN];
int rijeseno[MAXN];
bool provjeri = false;
long long update(int x){
x += OFF;
long long ans = tour[x];
x/=2;
while(x>0){
ans += tour[x];
x/=2;
}
return ans;
}
void query(int a, int b,int v, int x = 1, int lo = 0, int hi = OFF){
// cout << a << ' ' << b << ' ' << v << ' ' << x << ' ' <<lo << ' ' << hi << "\n";
if(b<=lo||hi<=a){
return;
}
if(lo>=a&&hi<=b){
tour[x] += v;
return;
}
int mid = (lo+hi)/2;
query(a,b,v,x*2,lo,mid);
query(a,b,v,x*2+1,mid,hi);
}
void bs(int lo, int hi, vector<int> stations) {
// cout << lo << ' ' << hi << "\n";
if(hi <= lo + 1 && provjeri == false) {
for(int i = 0; i < stations.size(); i++) {
if(middle[stations[i]] == -2) {
middle[stations[i]]++;
continue;
}
middle[stations[i]] = lo;
}
return;
}
// cout << lo << ' ' << hi << "\n";
int mid = (lo + hi) / 2;
for (int i = 0; i < mid; i++) {
if(l[i] <= r[i]) query(l[i] - 1,r[i],xi[i]);
else {
query(l[i] - 1,m,xi[i]);
query(0,r[i],xi[i]);
}
}
// for (int i = 0; i < m; i++) cout << update(i) << ' ';
// cout << "\n";
vector<int> lijevo,desno;
for (int i = 0; i < stations.size(); i++) {
zbroj[stations[i]] = 0;
for (int j = 0; j < sektori[stations[i]].size(); j++) {
zbroj[stations[i]] += update(sektori[stations[i]][j]);
if(zbroj[stations[i]] > zadvoljstvo[stations[i]]) break;
}
if(zbroj[stations[i]] < zadvoljstvo[stations[i]]) desno.push_back(stations[i]);
else lijevo.push_back(stations[i]);
if(provjeri) continue;
if(zbroj[stations[i]] == zadvoljstvo[stations[i]]) middle[stations[i]] = mid;
if(zbroj[stations[i]] < zadvoljstvo[stations[i]] && mid >= k) middle[stations[i]]= -2;
}
// cout << mid << "\n";
// for (int i = 0; i < stations.size(); i++) cout << zbroj[i] << ' ';
// cout << "\n";
if(provjeri == true) {
for (int i = 0; i < desno.size(); i++) middle[desno[i]] = -1;
return;
}
bs(mid + 1, hi, desno);
for (int i = 0; i < mid; i++) {
if(l[i] <= r[i]) query(l[i] - 1,r[i],(-1) * xi[i]);
else {
query(l[i] - 1,m,(-1) * xi[i]);
query(0,r[i],(-1) * xi[i]);
}
}
bs(lo, mid, lijevo);
}
int main() {
memset(middle,-1,sizeof(middle));
// ios_base::sync_with_stdio(false);
// cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> pripadnost[i];
for (int i = 0; i < m; i++) sektori[pripadnost[i] - 1].push_back(i);
for (int i = 0; i < n; i++) cin >> zadvoljstvo[i];
cin >> k;
for (int i = 0; i < k; i++) cin >> l[i] >> r[i] >> xi[i];
vector<int> stanice;
for (int i = 0; i < n; i++) stanice.push_back(i);
bs(1,k + 1,stanice);
memset(tour,0,sizeof(tour));
provjeri = true;
bs(k, k + 1,stanice);
for (int i = 0; i < n; i++) {
if(middle[i] == -1) cout << "NIE" << "\n";
else cout << middle[i] << "\n";
}
return 0;
}
Compilation message
met.cpp: In function 'void bs(int, int, std::vector<int>)':
met.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < stations.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
met.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < stations.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
met.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int j = 0; j < sektori[stations[i]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < desno.size(); i++) middle[desno[i]] = -1;
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
18028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
18028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6032 ms |
12532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6046 ms |
12140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6025 ms |
12012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6051 ms |
11628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6053 ms |
26456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6082 ms |
25728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
