| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 421510 |
2021-06-09T08:34:42 Z |
조영욱(#7654) |
Bubble Sort 2 (JOI18_bubblesort2) |
C++17 |
|
9000 ms |
116616 KB |
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=65536;
const int INF=1e9;
vector<int> pr;
struct SegmentTree {
int seg[sz*2];
int lazy[sz*2];
void init() {
for(int i=0;i<sz*2;i++) {
seg[i]=-INF;
}
}
void propagate(int node){
if (lazy[node]!=0) {
seg[node]+=lazy[node];
if (node<sz) {
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
}
int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
propagate(node);
if (r<nodel||l>noder) {
return -INF;
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int l,int r,int val,int node=1,int nodel=0,int noder=sz-1) {
propagate(node);
if (r<nodel||l>noder) {
return;
}
if (l<=nodel&&noder<=r) {
lazy[node]+=val;
propagate(node);
return;
}
int mid=(nodel+noder)/2;
update(l,r,val,node*2,nodel,mid);
update(l,r,val,node*2+1,mid+1,noder);
seg[node]=max(seg[node*2],seg[node*2+1]);
}
};
SegmentTree st[101];
struct FenwickTree {
int tree[sz];
int sum(int i) {
int ret=0;
while (i>0){
ret+=tree[i];
i-=(i&-i);
}
return ret;
}
void update(int i,int val) {
while (i<sz) {
tree[i]+=val;
i+=(i&-i);
}
}
};
FenwickTree ft[101];
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V) {
int n=A.size();
int q=V.size();
for(int i=0;i<n;i++) {
pr.push_back(A[i]);
}
for(int i=0;i<q;i++) {
pr.push_back(V[i]);
}
pr.push_back(-1);
sort(pr.begin(),pr.end());
pr.erase(unique(pr.begin(),pr.end()),pr.end());
for(int i=0;i<pr.size();i++) {
st[i].init();
}
for(int i=0;i<n;i++) {
A[i]=lower_bound(pr.begin(),pr.end(),A[i])-pr.begin();
}
for(int i=0;i<q;i++) {
V[i]=lower_bound(pr.begin(),pr.end(),V[i])-pr.begin();
}
for(int i=0;i<n;i++) {
ft[A[i]].update(i+1,1);
}
for(int i=0;i<n;i++) {
int sum=0;
for(int j=A[i]+1;j<pr.size();j++) {
sum+=ft[j].sum(i);
}
st[A[i]].update(i+1,i+1,-st[A[i]].sum(i+1,i+1)+sum);
}
vector<int> ret(q);
for(int i=0;i<q;i++) {
int pos=X[i]+1;
for(int j=0;j<A[X[i]];j++) {
st[j].update(pos+1,n,-1);
}
ft[A[X[i]]].update(pos,-1);
st[A[X[i]]].update(pos,pos,-st[A[X[i]]].sum(pos,pos)-INF);
A[X[i]]=V[i];
for(int j=0;j<A[X[i]];j++) {
st[j].update(pos+1,n,1);
}
ft[A[X[i]]].update(pos,1);
int sum=0;
for(int j=A[X[i]]+1;j<pr.size();j++) {
sum+=ft[j].sum(X[i]);
}
//printf("%d\n",st[A[X[i]]].sum(pos,pos));
st[A[X[i]]].update(pos,pos,-st[A[X[i]]].sum(pos,pos)+sum);
//printf("%d %d\n",sum,st[A[X[i]]].sum(pos,pos));
int val=0;
for(int j=0;j<pr.size();j++) {
val=max(val,st[j].sum(1,n));
}
ret[i]=val;
}
return ret;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:89:18: 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<pr.size();i++) {
| ~^~~~~~~~~~
bubblesort2.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 j=A[i]+1;j<pr.size();j++) {
| ~^~~~~~~~~~
bubblesort2.cpp:122:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int j=A[X[i]]+1;j<pr.size();j++) {
| ~^~~~~~~~~~
bubblesort2.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j=0;j<pr.size();j++) {
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
92 ms |
106436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
92 ms |
106436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
536 ms |
89200 KB |
Output is correct |
| 2 |
Correct |
5267 ms |
103892 KB |
Output is correct |
| 3 |
Execution timed out |
9067 ms |
116616 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
92 ms |
106436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
