| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 347689 |
2021-01-13T10:23:17 Z |
Lukap |
Meteors (POI11_met) |
C++14 |
|
6000 ms |
31264 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],lazy[2 * OFF];
long long middle[MAXN];
int rijeseno[MAXN];
bool provjeri = false;
void prop(int x, long long lo, long long hi){
if(lazy[x]==0) return;
tour[x] += lazy[x]*(hi-lo);
if(x<OFF){
lazy[2*x] += lazy[x];
lazy[2*x+1] += lazy[x];
}
lazy[x] = 0;
}
void update(int a, int b, int v, int x = 1, int lo = 0, int hi = OFF){
prop(x,lo,hi);
if(b<=lo||hi<=a) return;
if(lo>=a&&hi<=b){
lazy[x] = v;
prop(x,lo,hi);
return;
}
int mid = (lo+hi)/2;
update(a,b,v,2*x,lo,mid);
update(a,b,v,2*x+1,mid,hi);
tour[x] = tour[2*x]+tour[2*x+1];
}
long long query(int a, int b, int x = 1, int lo = 0, int hi = OFF){
// cout << a << ' ' << b << ' ' << x << ' ' << lo << ' ' << hi << "\n";
if(b<=lo||hi<=a) return 0;
prop(x,lo,hi);
if(lo>=a&&hi<=b) return tour[x];
int mid = (lo+hi)/2;
return query(a,b,2*x,lo,mid)+query(a,b,2*x+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]) update(l[i] - 1,r[i],xi[i]);
else {
update(l[i] - 1,m,xi[i]);
update(0,r[i],xi[i]);
}
}
for (int i = 0; i < stations.size(); i++) zbroj[stations[i]] = 0;
for (int i = 0; i < stations.size(); i++) {
for (int j = 0; j < sektori[stations[i]].size(); j++) {
zbroj[stations[i]] += query(sektori[stations[i]][j],sektori[stations[i]][j] + 1);
if(zbroj[stations[i]] > zadvoljstvo[stations[i]]) break;
}
}
vector<int> lijevo,desno;
// cout << mid << "\n";
for (int i = 0; i < stations.size(); i++) {
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;
}
// 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]) update(l[i] - 1,r[i],(-1) * xi[i]);
else {
update(l[i] - 1,m,(-1) * xi[i]);
update(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));
memset(lazy,0,sizeof(lazy));
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:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i < stations.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
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 i = 0; i < stations.size(); i++) zbroj[stations[i]] = 0;
| ~~^~~~~~~~~~~~~~~~~
met.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < stations.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
met.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int j = 0; j < sektori[stations[i]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = 0; i < stations.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
met.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < desno.size(); i++) middle[desno[i]] = -1;
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
316 ms |
26240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
373 ms |
26380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6067 ms |
13472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6038 ms |
12936 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6053 ms |
12780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6039 ms |
12524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6046 ms |
31264 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6031 ms |
30536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
