Task: | Final Array |
Sender: | O(n^10) |
Submission time: | 2019-05-25 13:44:10 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.22 s | details |
#2 | ACCEPTED | 0.14 s | details |
#3 | ACCEPTED | 0.03 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:41:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int64_t i2=0; i2<a[i].size(); i2++){ ~~^~~~~~~~~~~~ input/code.cpp:50:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int64_t i2=0; i2<l[i].size(); i2++){ ~~^~~~~~~~~~~~
Code
#include <bits/stdc++.h>using namespace std;#define F first#define S secondint64_t n,m;struct d{int64_t a,b,x;};int64_t puu[1<<18];int64_t size = 1<<18;vector<pair<int64_t,int64_t> > l[100000];vector<pair<int64_t,int64_t> > a[100000];int64_t ans[100000];void muuta(int64_t index, int64_t val){index += size/2;puu[index] = val;for(index/=2; index > 0; index/=2){puu[index] = max(puu[index*2],puu[index*2+1]);}}int main(){cin >> n >> m;for(int64_t i=0; i<size; i++){puu[i] = 0;}for(int64_t i=0; i<m; i++){int64_t aa,b;pair<int64_t,int64_t> x;cin >> aa>> b >> x.F;x.S = i;a[aa-1].push_back(x);l[b-1].push_back(x);}for(int64_t i=0; i<n; i++){for(int64_t i2=0; i2<a[i].size(); i2++){muuta(a[i][i2].S, a[i][i2].F-i);}if(puu[1] == 0){cout << "0 ";}else{cout << puu[1]+i << " ";}for(int64_t i2=0; i2<l[i].size(); i2++){muuta(l[i][i2].S,0);}}cout << "\n";}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
100000 100000 29706 39977 913671103 20575 89990 878449866 1691 70785 229168045 81099 81323 611730238 ... |
correct output |
---|
227121122 450258482 450258483 ... |
user output |
---|
227121122 450258482 450258483 ... Truncated |
Test 2
Verdict: ACCEPTED
input |
---|
100000 100000 1 100000 1 1 100000 2 1 100000 3 1 100000 4 ... |
correct output |
---|
100000 100001 100002 100003 10... |
user output |
---|
100000 100001 100002 100003 10... Truncated |
Test 3
Verdict: ACCEPTED
input |
---|
8 2 1 4 1 1 8 1 |
correct output |
---|
1 2 3 4 5 6 7 8 |
user output |
---|
1 2 3 4 5 6 7 8 |