oj.uz

답안 #851146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851146 2023-09-18T15:52:45 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 9000 ms 13616 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=2e5 + 3;
const int MOD=1e9+7;
const int off=(1<<20);

int mx[off*2],mn[off*2];
void upd(int x,int v){
	x+=off;
	mx[x]=v;
	mn[x]=v;
	while(x/=2){
		mx[x]=max(mx[x*2],mx[x*2+1]);
		if(mn[x*2]==0)mn[x*2]=INT_MAX;
		if(mn[x*2+1]==0)mn[x*2+1]=INT_MAX;
		mn[x]=min(mn[x*2],mn[x*2+1]);
	}
}
int get(int x,int l,int r,int st,int en,int val){
	if(r<st||l>en)return 0;
   if(l>=st&&r<=en){
      if(mn[x]>val)
      return r-l+1;
      if(mx[x]<=val)
      return 0;
   }
   int mid=(l+r)/2;
   return (get(x*2,l,mid,st,en,val)+get(x*2+1,mid+1,r,st,en,val));
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int q=X.size(),n=A.size();
	int dis[n];
   multiset<int>ms;
	vector<int>ans;
   for(int i=0;i<n;i++){
      int x=A[i];
      upd(i,x);
      dis[i]=get(1,1,off-1,0,i,x);
      ms.insert(dis[i]);
   }
   for(int j=0;j<q;j++){
      int x=X[j],v=V[j];

      upd(x,v);
      dis[x]=get(1,1,off-1,0,x,v);
      ms.insert(dis[x]);
      for(int i=x+1;i<n;i++){
         if(A[x]<=A[i]&&v>A[i]){
            ms.erase(ms.find(dis[i]));
            dis[i]++;
            // cout<<dis[i]<<endl;
            ms.insert(dis[i]);
         }
         if(A[x]>A[i]&&v<=A[i]){
            ms.erase(ms.find(dis[i]));
            dis[i]--;
            ms.insert(dis[i]);
         }
      }
      A[x]=v;
      ans.pb(*ms.rbegin());
   }
	return ans;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4634 ms 12956 KB Output is correct
2 Execution timed out 9096 ms 13616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -