oj.uz

Submission #253033

# Submission time Handle Problem Language Result Execution time Memory
253033 2020-07-26T17:12:34 Z rqi Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 7436 ms 207980 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		int mid = (lo+hi)/2; 
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

/**
 * Description: 1D range update and query, $SZ=2^p$.
 * Source: USACO Counting Haybales
 * Verification: SPOJ Horrible
 */

template<class T, int SZ> struct LazySeg { 
	T mx[2*SZ], lazy[2*SZ]; 
	LazySeg() { F0R(i,2*SZ) mx[i] = lazy[i] = 0; }
	void push(int ind, int L, int R) { /// modify values for current node
		if (L != R) F0R(i,2) lazy[2*ind+i] += lazy[ind]; /// prop to children
		mx[ind] += lazy[ind]; lazy[ind] = 0; 
	} // recalc values for current node
	void pull(int ind) { mx[ind] = max(mx[2*ind], mx[2*ind+1]); }
	void build() { ROF(i,1,SZ) pull(i); }
	void upd(int lo,int hi,T inc,int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) { 
			lazy[ind] = inc; push(ind,L,R); return; }
		int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M); 
		upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind);
	}
	T qmax(int lo, int hi, int ind=1, int L=0, int R = SZ-1) {
		push(ind,L,R); if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return mx[ind];
		int M = (L+R)/2; 
		return max(qmax(lo,hi,2*ind,L,M), qmax(lo,hi,2*ind+1,M+1,R));
	}
};

LazySeg<int, 1048576> lseg;

const int mx = 1000005;

set<int> maxind[mx];

void ERASE(int val){
	int mind = *(prev(maxind[val].end()));
	lseg.upd(val, val, -mind);
}

void INSERT(int val){
	int mind = *(prev(maxind[val].end()));
	lseg.upd(val, val, mind);
}

void updmaxind(int pval, int cval, int ind){
	if(pval != -1){
		lseg.upd(1, pval-1, -1);
		ERASE(pval);
		maxind[pval].erase(ind);
		INSERT(pval);
	}
	lseg.upd(1, cval-1, 1);
	ERASE(cval);
	maxind[cval].ins(ind);
	INSERT(cval);

}

vi countScans(vi A, vi X, vi V){
	int N = sz(A);
	int Q = sz(X);
	//seg.init(N+Q+5);

	map<int, int> m;
	for(auto u: A){
		m[u];
	}
	for(auto u: V){
		m[u];
	}

	int cnt = 0;
	for(auto &u: m){
		u.s = ++cnt;
	}
	for(auto &u: A){
		u = m[u];
	}
	for(auto &u: V){
		u = m[u];
	}

	vi answer(Q);

	// for(int i = 1; i <= 4; i++){
	// 	ps(i, lseg.qmax(i, i));
	// }

	for(int i = 0; i < mx; i++){
		maxind[i].ins(-MOD);
		lseg.upd(i, i, 0-(N-1)-MOD);
	}

	for(int i = 0; i < N; i++){
		updmaxind(-1, A[i], i);
	}

	for(int j = 0; j < Q; j++){
		updmaxind(A[X[j]], V[j], X[j]);
		A[X[j]] = V[j];
		int ans = lseg.qmax(1, mx-1);
		answer[j] = ans;
	}

	return answer;
}

// int main(){
// 	ps(countScans(vi{1, 2, 3, 4}, vi{0, 2}, vi{3, 1}));
// }

Compilation message

bubblesort2.cpp: In function 'void setIn(std::__cxx11::string)':
bubblesort2.cpp:129:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp: In function 'void setOut(std::__cxx11::string)':
bubblesort2.cpp:130:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 110712 KB Output is correct
2 Correct 326 ms 110844 KB Output is correct
3 Correct 320 ms 111096 KB Output is correct
4 Correct 320 ms 111096 KB Output is correct
5 Correct 312 ms 111096 KB Output is correct
6 Correct 310 ms 111096 KB Output is correct
7 Correct 327 ms 111144 KB Output is correct
8 Correct 312 ms 111100 KB Output is correct
9 Correct 316 ms 111096 KB Output is correct
10 Correct 314 ms 110968 KB Output is correct
11 Correct 313 ms 111096 KB Output is correct
12 Correct 335 ms 110968 KB Output is correct
13 Correct 317 ms 111096 KB Output is correct
14 Correct 323 ms 110968 KB Output is correct
15 Correct 311 ms 110968 KB Output is correct
16 Correct 323 ms 111128 KB Output is correct
17 Correct 328 ms 111096 KB Output is correct
18 Correct 331 ms 111108 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 110712 KB Output is correct
2 Correct 326 ms 110844 KB Output is correct
3 Correct 320 ms 111096 KB Output is correct
4 Correct 320 ms 111096 KB Output is correct
5 Correct 312 ms 111096 KB Output is correct
6 Correct 310 ms 111096 KB Output is correct
7 Correct 327 ms 111144 KB Output is correct
8 Correct 312 ms 111100 KB Output is correct
9 Correct 316 ms 111096 KB Output is correct
10 Correct 314 ms 110968 KB Output is correct
11 Correct 313 ms 111096 KB Output is correct
12 Correct 335 ms 110968 KB Output is correct
13 Correct 317 ms 111096 KB Output is correct
14 Correct 323 ms 110968 KB Output is correct
15 Correct 311 ms 110968 KB Output is correct
16 Correct 323 ms 111128 KB Output is correct
17 Correct 328 ms 111096 KB Output is correct
18 Correct 331 ms 111108 KB Output is correct
19 Correct 345 ms 111992 KB Output is correct
20 Correct 366 ms 112248 KB Output is correct
21 Correct 382 ms 112248 KB Output is correct
22 Correct 401 ms 112252 KB Output is correct
23 Correct 351 ms 112120 KB Output is correct
24 Correct 371 ms 112248 KB Output is correct
25 Correct 358 ms 112120 KB Output is correct
26 Correct 347 ms 112120 KB Output is correct
27 Correct 347 ms 111992 KB Output is correct
28 Correct 341 ms 112108 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 112372 KB Output is correct
2 Correct 455 ms 113772 KB Output is correct
3 Correct 607 ms 114936 KB Output is correct
4 Correct 558 ms 115048 KB Output is correct
5 Correct 590 ms 114936 KB Output is correct
6 Correct 574 ms 114936 KB Output is correct
7 Correct 540 ms 115016 KB Output is correct
8 Correct 590 ms 115064 KB Output is correct
9 Correct 582 ms 114936 KB Output is correct
10 Correct 509 ms 115064 KB Output is correct
11 Correct 549 ms 115064 KB Output is correct
12 Correct 547 ms 115268 KB Output is correct
13 Correct 505 ms 115064 KB Output is correct
14 Correct 519 ms 115184 KB Output is correct
15 Correct 529 ms 115192 KB Output is correct
16 Correct 502 ms 115156 KB Output is correct
17 Correct 519 ms 115032 KB Output is correct
18 Correct 527 ms 115196 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 110712 KB Output is correct
2 Correct 326 ms 110844 KB Output is correct
3 Correct 320 ms 111096 KB Output is correct
4 Correct 320 ms 111096 KB Output is correct
5 Correct 312 ms 111096 KB Output is correct
6 Correct 310 ms 111096 KB Output is correct
7 Correct 327 ms 111144 KB Output is correct
8 Correct 312 ms 111100 KB Output is correct
9 Correct 316 ms 111096 KB Output is correct
10 Correct 314 ms 110968 KB Output is correct
11 Correct 313 ms 111096 KB Output is correct
12 Correct 335 ms 110968 KB Output is correct
13 Correct 317 ms 111096 KB Output is correct
14 Correct 323 ms 110968 KB Output is correct
15 Correct 311 ms 110968 KB Output is correct
16 Correct 323 ms 111128 KB Output is correct
17 Correct 328 ms 111096 KB Output is correct
18 Correct 331 ms 111108 KB Output is correct
19 Correct 345 ms 111992 KB Output is correct
20 Correct 366 ms 112248 KB Output is correct
21 Correct 382 ms 112248 KB Output is correct
22 Correct 401 ms 112252 KB Output is correct
23 Correct 351 ms 112120 KB Output is correct
24 Correct 371 ms 112248 KB Output is correct
25 Correct 358 ms 112120 KB Output is correct
26 Correct 347 ms 112120 KB Output is correct
27 Correct 347 ms 111992 KB Output is correct
28 Correct 341 ms 112108 KB Output is correct
29 Correct 378 ms 112372 KB Output is correct
30 Correct 455 ms 113772 KB Output is correct
31 Correct 607 ms 114936 KB Output is correct
32 Correct 558 ms 115048 KB Output is correct
33 Correct 590 ms 114936 KB Output is correct
34 Correct 574 ms 114936 KB Output is correct
35 Correct 540 ms 115016 KB Output is correct
36 Correct 590 ms 115064 KB Output is correct
37 Correct 582 ms 114936 KB Output is correct
38 Correct 509 ms 115064 KB Output is correct
39 Correct 549 ms 115064 KB Output is correct
40 Correct 547 ms 115268 KB Output is correct
41 Correct 505 ms 115064 KB Output is correct
42 Correct 519 ms 115184 KB Output is correct
43 Correct 529 ms 115192 KB Output is correct
44 Correct 502 ms 115156 KB Output is correct
45 Correct 519 ms 115032 KB Output is correct
46 Correct 527 ms 115196 KB Output is correct
47 Correct 2057 ms 139704 KB Output is correct
48 Correct 5390 ms 198508 KB Output is correct
49 Correct 7150 ms 207704 KB Output is correct
50 Correct 6630 ms 207616 KB Output is correct
51 Correct 7436 ms 207672 KB Output is correct
52 Correct 7104 ms 207652 KB Output is correct
53 Correct 7130 ms 207736 KB Output is correct
54 Correct 6268 ms 207744 KB Output is correct
55 Correct 5868 ms 207980 KB Output is correct
56 Correct 5279 ms 207716 KB Output is correct
57 Correct 5716 ms 207736 KB Output is correct
58 Correct 5656 ms 207812 KB Output is correct
59 Correct 4723 ms 200724 KB Output is correct
60 Correct 4862 ms 200932 KB Output is correct
61 Correct 4752 ms 200568 KB Output is correct
62 Correct 4700 ms 197596 KB Output is correct
63 Correct 4720 ms 197684 KB Output is correct
64 Correct 4830 ms 197772 KB Output is correct
65 Correct 5107 ms 194580 KB Output is correct
66 Correct 4451 ms 194440 KB Output is correct
67 Correct 4649 ms 194580 KB Output is correct