oj.uz

Submission #145587

# Submission time Handle Problem Language Result Execution time Memory
145587 2019-08-20T12:55:14 Z bharat2002 Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 96 ms 49400 KB 
/*input

*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6 + 1099;
const int mod=1e9 + 7;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
int n;map<int, int> conv; 
multiset<int> positions[N];
class tree
{
	int tree[4*N], lazy[4*N], ql, qr, val;
	void prop(int i, int l, int r)
	{
		tree[i]+=lazy[i];
		if(l!=r)
		{
			lazy[2*i]+=lazy[i];lazy[2*i+1]+=lazy[i];
		}
		lazy[i]=0;
	}
	void update(int i=1, int l=1, int r=N-1)
	{
		prop(i, l, r);
		if(l>qr||r<ql) return;
		if(l>=ql&&r<=qr)
		{
			lazy[i]+=val;prop(i, l, r);
			return;
		}
		int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);tree[i]=max(tree[2*i], tree[2*i+1]);
	}
	int query(int i=1, int l=1, int r=N-1)
	{
		prop(i, l, r);
		if(l>qr||r<ql) return 0;
		if(l>=ql&&r<=qr)
		{
			return tree[i];
		}
		int mid=(l+r)>>1;
		int v1=query(2*i, l, mid), v2=query(2*i+1, mid+1, r);
		tree[i]=max(tree[2*i], tree[2*i+1]);return max(v1, v2);
	}
	public:
	void remove(int ind, int el)
	{
		int prevmax=(*positions[el].rbegin());
		positions[el].erase(ind);
		if(!positions[el].empty()) prevmax=(*positions[el].rbegin()) - prevmax;
		else prevmax*=-1;
		ql=qr=el;val=prevmax;
		if(val!=0) update();
		ql=el+1;qr=N-1;val=+1;update();
	}
	void add(int ind, int el)
	{
		int prevmax=0;
		if(!positions[el].empty()) prevmax=(*positions[el].rbegin());
		positions[el].insert(ind);
		prevmax=(*positions[el].rbegin() - prevmax);
		ql=qr=el;val=prevmax;
		if(val!=0) update();
		ql=el+1;qr=N-1;val=-1;update();
	}
	int qry()
	{
		ql=1;qr=N-1;return query();
	}
};
tree Segtree;
vector<int> countScans(vector<int> arr, vector<int> pos, vector<int> nval)
{
	n=arr.size();int q=pos.size();vector<int> ans;
	conv.clear();
	for(auto i:arr) conv[i]=0;
	for(auto i:nval) conv[i]=0;
	int curv=1;
	for(auto &i:conv) i.s=curv++;
	for(int i=0;i<n;i++) {arr[i]=conv[arr[i]];Segtree.add(i, arr[i]);}
	for(auto &i:nval) i=conv[i];
//	cout<<Segtree.qry()<<endl;
	for(int i=0;i<q;i++)
	{
		Segtree.remove(pos[i], arr[pos[i]]);
		Segtree.add(pos[i], nval[i]);arr[pos[i]]=nval[i];
		ans.push_back(Segtree.qry());
	}
	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47608 KB Output is correct
2 Correct 49 ms 47736 KB Output is correct
3 Correct 54 ms 47868 KB Output is correct
4 Correct 53 ms 47912 KB Output is correct
5 Correct 53 ms 47864 KB Output is correct
6 Correct 53 ms 47920 KB Output is correct
7 Correct 53 ms 47864 KB Output is correct
8 Correct 53 ms 47992 KB Output is correct
9 Correct 54 ms 47992 KB Output is correct
10 Correct 53 ms 47892 KB Output is correct
11 Correct 53 ms 47836 KB Output is correct
12 Correct 55 ms 47864 KB Output is correct
13 Correct 53 ms 47864 KB Output is correct
14 Correct 53 ms 47864 KB Output is correct
15 Correct 59 ms 47840 KB Output is correct
16 Correct 60 ms 47868 KB Output is correct
17 Correct 55 ms 47864 KB Output is correct
18 Correct 61 ms 47864 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47608 KB Output is correct
2 Correct 49 ms 47736 KB Output is correct
3 Correct 54 ms 47868 KB Output is correct
4 Correct 53 ms 47912 KB Output is correct
5 Correct 53 ms 47864 KB Output is correct
6 Correct 53 ms 47920 KB Output is correct
7 Correct 53 ms 47864 KB Output is correct
8 Correct 53 ms 47992 KB Output is correct
9 Correct 54 ms 47992 KB Output is correct
10 Correct 53 ms 47892 KB Output is correct
11 Correct 53 ms 47836 KB Output is correct
12 Correct 55 ms 47864 KB Output is correct
13 Correct 53 ms 47864 KB Output is correct
14 Correct 53 ms 47864 KB Output is correct
15 Correct 59 ms 47840 KB Output is correct
16 Correct 60 ms 47868 KB Output is correct
17 Correct 55 ms 47864 KB Output is correct
18 Correct 61 ms 47864 KB Output is correct
19 Correct 75 ms 49056 KB Output is correct
20 Correct 80 ms 49276 KB Output is correct
21 Correct 85 ms 49400 KB Output is correct
22 Correct 92 ms 49272 KB Output is correct
23 Correct 87 ms 49144 KB Output is correct
24 Correct 78 ms 49148 KB Output is correct
25 Correct 79 ms 49112 KB Output is correct
26 Correct 90 ms 49144 KB Output is correct
27 Correct 91 ms 49116 KB Output is correct
28 Correct 86 ms 49016 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 49124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47608 KB Output is correct
2 Correct 49 ms 47736 KB Output is correct
3 Correct 54 ms 47868 KB Output is correct
4 Correct 53 ms 47912 KB Output is correct
5 Correct 53 ms 47864 KB Output is correct
6 Correct 53 ms 47920 KB Output is correct
7 Correct 53 ms 47864 KB Output is correct
8 Correct 53 ms 47992 KB Output is correct
9 Correct 54 ms 47992 KB Output is correct
10 Correct 53 ms 47892 KB Output is correct
11 Correct 53 ms 47836 KB Output is correct
12 Correct 55 ms 47864 KB Output is correct
13 Correct 53 ms 47864 KB Output is correct
14 Correct 53 ms 47864 KB Output is correct
15 Correct 59 ms 47840 KB Output is correct
16 Correct 60 ms 47868 KB Output is correct
17 Correct 55 ms 47864 KB Output is correct
18 Correct 61 ms 47864 KB Output is correct
19 Correct 75 ms 49056 KB Output is correct
20 Correct 80 ms 49276 KB Output is correct
21 Correct 85 ms 49400 KB Output is correct
22 Correct 92 ms 49272 KB Output is correct
23 Correct 87 ms 49144 KB Output is correct
24 Correct 78 ms 49148 KB Output is correct
25 Correct 79 ms 49112 KB Output is correct
26 Correct 90 ms 49144 KB Output is correct
27 Correct 91 ms 49116 KB Output is correct
28 Correct 86 ms 49016 KB Output is correct
29 Incorrect 96 ms 49124 KB Output isn't correct
30 Halted 0 ms 0 KB -