| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1040719 |
2024-08-01T08:43:56 Z |
1557중연결요소(#11043) |
Tricks of the Trade (CEOI23_trade) |
C++17 |
|
9 ms |
21448 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int A[250005];
int B[250005];
int C[250005];
int D[250005];
vector<array<int, 2>> V;
int ans = -INF;
int K;
int F[250005];
struct SegTree {
struct Node {
int l, r, cnt, sum;
Node():l(-1),r(-1),cnt(0),sum(0) {}
Node(int c) : l(-1), r(-1), cnt(1), sum(c) {}
};
vector<Node> seg;
vector<int> root;
int MAX;
void init(int N) {
int i;
for(i=1;i<N;i*=2) {}
MAX = i;
seg.clear();
root.clear();
root.push_back(cons(0, MAX));
}
int cons(int s, int e) {
Node c = Node();
int v = seg.size();
seg.push_back(c);
int mid = s + e >> 1;
//cout << s << ' ' << e << ' ' << v << '\n';
if(e == s + 1) return v;
if(s != mid) {
int l1 = cons(s, mid);
int r1 = cons(mid, e);
seg[v].l = l1, seg[v].r = r1;
}
//cout << s << ' ' << e << ' ' << v << '\n';
//cout << seg[v].l <<' ' << seg[v].r << '\n';
assert(v != -1);
return v;
}
int add(int k, int v, int n, int ns, int ne) {
Node c = Node();
int cc= seg[n].cnt + 1;
int cs= seg[n].sum + v;
int cl = seg[n].l, cr = seg[n].r;
c.cnt = cc, c.sum = cs, c.l = cl, c.r = cr;
//cout << k << ' ' << v << ' ' << n << ' ' << ns << ' ' << ne << '\n';
int num = seg.size();
seg.push_back(c);
if(ns+1==ne) {
return num;
}
int mid = ns + ne >> 1;
if(mid <= k) {
int v1 = add(k, v, seg[n].r, mid, ne);
seg[num].r = v1;
return num;
}
else {
int v1 = add(k, v, seg[n].l, ns, mid);
seg[num].l = v1;
return num;
}
}
int add_node(int k, int v) {
//cout << "ADD:" << k << ' ' << v << '\n';
root.push_back(add(k, v, root.back(), 0, MAX));
}
int get_val(int n1, int n2, int ns, int ne, int k) {
//cout << n1 << ' ' << n2 <<' ' << ns << ' ' << ne << ' ' << k << '\n';
if(k==0) return 0;
if(ns+1==ne) return seg[n1].sum - seg[n2].sum;
int r1 = seg[n1].r, r2 = seg[n2].r;
assert(r1 != -1 && r2 != -1);
int v = seg[r1].cnt - seg[r2].cnt;
if(v==k) {
int res = seg[r1].sum - seg[r2].sum;
//cout << n1 << ' ' << n2 << ' ' << res << '\n';
return res;
}
int mid = ns + ne >> 1;
if(v < k) {
int res = seg[r1].sum - seg[r2].sum + get_val(seg[n1].l, seg[n2].l, ns, mid, k-v);
//cout << n1 << ' ' << n2 << ' ' << res << '\n';
return res;
}
int res = get_val(r1, r2, mid, ne, k);
//cout << n1 << ' ' << n2 << ' ' << res << '\n';
return res;
}
int get_calc(int s, int e, int k) {
int res = get_val(root[e+1], root[s], 0, MAX, k);
//cout << s+1 << ' ' << e+1 << " : " << res << '\n';
return res;
}
};
SegTree tree;
int G[250005];
void tree_cons(int N) {
int i, j;
tree.init(N+3);
/*cout << "init done\n";
for(i=0;i<tree.seg.size();i++) {
cout << i << " : " << tree.seg[i].l <<' ' << tree.seg[i].r << ' ' << tree.seg[i].cnt <<' ' << tree.seg[i].sum << '\n';
}
for(i=0;i<tree.root.size();i++) cout <<tree.root[i] << ' ';
cout << '\n';*/
vector<array<int, 2>> V2;
for(i=0;i<N;i++) V2.push_back({B[i], i});
sort(V2.begin(),V2.end());
for(i=0;i<N;i++) G[V2[i][1]] = i;
for(i=0;i<N;i++) tree.add_node(G[i], B[i]);
/*for(i=0;i<tree.seg.size();i++) {
cout << i << " : " << tree.seg[i].l <<' ' << tree.seg[i].r << ' ' << tree.seg[i].cnt <<' ' << tree.seg[i].sum << '\n';
}
for(i=0;i<tree.root.size();i++) cout <<tree.root[i] << ' ';
cout << '\n';*/
}
int calc_val(int s, int e) {
int res = tree.get_calc(s, e, K) - (F[e] - (s-1>=0?F[s-1]:0));
//cout << s+1 <<' ' << e+1 << " : " << res <<'\n';
return res;
}
void calc(int s, int e) {
int i, j;
int ma = -INF, id = -1;
priority_queue<int, vector<int>, greater<int>> PQ;
int sum = 0;
for(i=s;i<=e;i++) {
sum -= A[i];
bool isok = false;
if(PQ.size() == K-1) isok = true;
if(PQ.size() == K && PQ.top() <= B[i]) isok = true;
PQ.push(B[i]);
sum += B[i];
if(PQ.size() > K) {
sum -= PQ.top();
PQ.pop();
}
if(PQ.size() < K) continue;
if(sum > ma) {
ma = sum;
id = i;
}
if(sum > ans) {
ans = sum;
V.clear();
}
if(ans == sum && isok) {
V.push_back({s, i});
}
}
}
void DnC(int s, int e, int a, int b) {
if(s>e) return;
int i, j;
a = max(a, s+K-1);
int mid = s + e >> 1;
int ma = -INF, id = b;
//cout <<"DNC: " << s << ' ' << e << ' ' << a << ' ' << b << '\n';
for(i=max(mid+K-1, a); i <= b; i++) {
int v = calc_val(mid, i);
if(v > ma) {
ma = v;
id = i;
}
}
C[mid] = ma, D[mid] = id;
if(ma > ans) ans = ma;
DnC(s, mid-1, a, id);
DnC(mid+1, e, id, b);
}
int E[250005];
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N >> K;
int i, j;
for(i=0;i<N;i++) cin >> A[i];
for(i=0;i<N;i++) F[i] = A[i];
for(i=1;i<N;i++) F[i] += F[i-1];
for(i=0;i<N;i++) cin >> B[i];
tree_cons(N);
DnC(0, N-1, 0, N-1);
vector<int> pos;
for(i=0;i<N;i++) {
if(C[i]==ans) pos.push_back(i);
}
pos.push_back(N);
//cout << ans << '\n';
for(int i=0;i<pos.size();i++) {
int n = pos[i];
if(n==N) continue;
V.push_back({n, D[n]});
if(D[n]+1<pos[i+1]) {
calc(pos[i], pos[i+1]-1);
}
}
vector<vector<array<int, 2>>> in, out;
in.resize(N);
out.resize(N);
int cnt = 0;
for(auto k : V) {
//k[0] ~ k[1]
// kth element <= a[i] -> ?
int v = (ans + F[k[1]] - (k[0]-1>=0?F[k[0]-1]:0)) - tree.get_calc(k[0], k[1], K-1);
in[k[0]].push_back({v, cnt});
out[k[1]].push_back({v, cnt});
cnt++;
}
/*for(i=0;i<N;i++) cout << D[i] <<' ';
cout << '\n';
for(auto k : V) cout << k[0]+1 << ' ' << k[1]+1 << '\n';*/
cout << ans <<'\n';
set<array<int, 2>> S;
for(i=0;i<N;i++) {
for(auto n : in[i]) {
S.insert(n);
}
if(!S.empty() && B[i] >= (*S.begin())[0]) cout << "1";
else cout << "0";
for(auto n : out[i]) {
S.erase(n);
}
}
}
Compilation message
trade.cpp: In member function 'long long int SegTree::cons(long long int, long long int)':
trade.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid = s + e >> 1;
| ~~^~~
trade.cpp: In member function 'long long int SegTree::add(long long int, long long int, long long int, long long int, long long int)':
trade.cpp:59:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = ns + ne >> 1;
| ~~~^~~~
trade.cpp: In member function 'long long int SegTree::add_node(long long int, long long int)':
trade.cpp:74:5: warning: no return statement in function returning non-void [-Wreturn-type]
74 | }
| ^
trade.cpp: In member function 'long long int SegTree::get_val(long long int, long long int, long long int, long long int, long long int)':
trade.cpp:87:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = ns + ne >> 1;
| ~~~^~~~
trade.cpp: In function 'void tree_cons(long long int)':
trade.cpp:106:12: warning: unused variable 'j' [-Wunused-variable]
106 | int i, j;
| ^
trade.cpp: In function 'void calc(long long int, long long int)':
trade.cpp:138:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
138 | if(PQ.size() == K-1) isok = true;
| ~~~~~~~~~~^~~~~~
trade.cpp:139:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
139 | if(PQ.size() == K && PQ.top() <= B[i]) isok = true;
| ~~~~~~~~~~^~~~
trade.cpp:142:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
142 | if(PQ.size() > K) {
| ~~~~~~~~~~^~~
trade.cpp:146:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
146 | if(PQ.size() < K) continue;
| ~~~~~~~~~~^~~
trade.cpp:131:12: warning: unused variable 'j' [-Wunused-variable]
131 | int i, j;
| ^
trade.cpp:132:20: warning: variable 'id' set but not used [-Wunused-but-set-variable]
132 | int ma = -INF, id = -1;
| ^~
trade.cpp: In function 'void DnC(long long int, long long int, long long int, long long int)':
trade.cpp:164:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
164 | int mid = s + e >> 1;
| ~~^~~
trade.cpp:162:12: warning: unused variable 'j' [-Wunused-variable]
162 | int i, j;
| ^
trade.cpp: In function 'int main()':
trade.cpp:199:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for(int i=0;i<pos.size();i++) {
| ~^~~~~~~~~~~
trade.cpp:186:12: warning: unused variable 'j' [-Wunused-variable]
186 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
21448 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
21448 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
