oj.uz

Submission #942217

# Submission time Handle Problem Language Result Execution time Memory
942217 2024-03-10T11:14:17 Z Litusiano Pilot (NOI19_pilot) C++14
31 / 100
 183 ms 33364 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6+5;

int calc(pair<int,int> p){
	int len = p.second - p.first +1;
	return (len*(len+1))/2;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m; cin>>n>>m;
	vector<int> v(n); for(int& i : v) cin>>i;
	vector<int> b(m); for(int& i : b) cin>>i;
	set<pair<int,int>> segs; segs.insert({0,n-1}); segs.insert({n,n});
	vector<vector<int>> ST(MAXN);
	for(int i = 0; i<m; i++) ST[b[i]].push_back(i); // indexed one more
	for(int i = 0; i<n; i++) ST[v[i]].push_back(-i-1);
	int ans = n*(n+1)/2;
	vector<int> q(m);
	for(int j = MAXN-1; j>=0; j--){
		for(auto i : ST[j]){
			if(i < 0){
				// cur seg
				if(segs.size() == 0) continue;
				int x = -i -1;//i+1
				pair<int,int> p = {x, 0};
				auto it = segs.upper_bound(p);
				if(it != segs.begin()) it = prev(it);
				pair<int,int> p1 = *it;
				// divide p1 in two
				int len = p1.second - p1.first +1;
				ans -= (len*(len+1))/2;
				pair<int,int> seg1; pair<int,int> seg2;
				seg1 = {p1.first, x-1}; seg2 = {x+1, p1.second};
				// cerr<<"X: "<<x<<" J: "<<j<<" P1 "<<p1.first<<" "<<p1.second<<" SEG1 "<<seg1.first<<" "<<seg1.second<<" SEG2 "<<seg2.first<<" "<<seg2.second<<endl;
				if(seg1.second >= seg1.first) segs.insert(seg1), ans+= calc(seg1);
				if(seg2.second >= seg2.first) segs.insert(seg2), ans+= calc(seg2);
				segs.erase(p1);
				// cerr<<"SEGS: ";
				// for(auto z : segs) cout<<z.first<<" "<<z.second<<"  "; cout<<endl;
			}
			else{
				q[i] = ans;
			}
		}
	}
	for(int i : q) cout<<i<<endl;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Incorrect 10 ms 23896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Incorrect 10 ms 23896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Incorrect 10 ms 23896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 30000 KB Output is correct
2 Correct 113 ms 31132 KB Output is correct
3 Correct 95 ms 29780 KB Output is correct
4 Correct 85 ms 30548 KB Output is correct
5 Correct 77 ms 29780 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 32544 KB Output is correct
2 Correct 152 ms 32516 KB Output is correct
3 Correct 155 ms 32564 KB Output is correct
4 Correct 145 ms 32548 KB Output is correct
5 Correct 148 ms 32560 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 33364 KB Output is correct
2 Correct 153 ms 33108 KB Output is correct
3 Correct 183 ms 33108 KB Output is correct
4 Correct 152 ms 33108 KB Output is correct
5 Correct 159 ms 33320 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Correct 84 ms 30000 KB Output is correct
12 Correct 113 ms 31132 KB Output is correct
13 Correct 95 ms 29780 KB Output is correct
14 Correct 85 ms 30548 KB Output is correct
15 Correct 77 ms 29780 KB Output is correct
16 Incorrect 85 ms 29720 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Incorrect 10 ms 23896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23900 KB Output is correct
2 Correct 17 ms 23900 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 8 ms 23900 KB Output is correct
6 Correct 8 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Incorrect 10 ms 23896 KB Output isn't correct
12 Halted 0 ms 0 KB -