oj.uz

Submission #614049

# Submission time Handle Problem Language Result Execution time Memory
614049 2022-07-30T17:25:36 Z IWTIM Osumnjičeni (COCI21_osumnjiceni) C++14
110 / 110
 633 ms 68596 KB 
# include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk 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 rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 998244353;
const int MX = 2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
#define f first
#define s second
#define int long long
#define pb push_back
const int N = 4e5+5;
int n,l[200005],r[200005],mnle,mxri,ans,q,le,ri,prle,nxt[200005],cnt,curri,p[200005][20];
int tree[2*N],tree1[2*N];
unordered_map <int, int> mp;
vector <int> v;
void update(int idx, int val) {
	for (int i = idx; i < N; i+=i&(-i)) {
		tree[i] += val;
	}
}
int getans(int idx) {
	int pas = 0;
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree[i];
	}
	return pas;
}
void update1(int idx, int val) {
	for (int i = idx; i < N; i+=i&(-i)) {
		tree1[i] += val;
	}
}
int getans1(int idx) {
	int pas = 0;
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree1[i];
	}
	return pas;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i = 1; i <= n; i++) {
		cin>>l[i]>>r[i];
		v.pb(l[i]);
		v.pb(r[i]);
	}
	sort(v.begin(),v.end());
	mp[v[0]] = 1;
	cnt = 1;
	for (int i = 1; i < v.size() ;i++) {
		if (v[i] != v[i - 1]) cnt++;
		mp[v[i]] = cnt;
	}
	for (int i = 1; i <= n; i++) {
		l[i] = mp[l[i]];
		r[i] = mp[r[i]];
	}
	curri = 0;
	for (int i = 1; i <= n; i++) {
		if (i > curri) {
			curri = i;
			update(l[i],1);
			update(r[i] + 1, -1);
			update1(l[i],1);
		}
		while (curri < n) {
			curri++;
			if (getans(l[curri]) <= 0 && getans1(r[curri]) - getans1(l[curri]-1) <= 0) {
				update(l[curri],1); update(r[curri]+1, -1);
				update1(l[curri],1);
			} else {
				curri--;
				break;
			}
		}
		p[i][0] = curri;
		update(l[i],-1); update(r[i] + 1, 1); update1(l[i],-1);
	}
	for (int j = 1; j <= 18; j++) {
		for (int i = 1; i <= n; i++) {
		     if (p[i][j-1] == n) {
		     	p[i][j] = n;
			 } else
			p[i][j] = p[p[i][j-1] + 1][j-1];
		}
	}
	cin>>q;
	for (int i = 1; i <= q; i++) {
		cin>>le>>ri;
		ans = 0;
		int cur = le;
		for (int j = 18; j >= 0; j--) {
			if (p[cur][j] < ri) {
				cur = p[cur][j] + 1;
				ans += (1<<j);
			}
		}
		cout<<ans + 1<<"\n";
	}
}

Compilation message

Main.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:143:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for (int i = 1; i < v.size() ;i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 63484 KB Output is correct
2 Correct 299 ms 62584 KB Output is correct
3 Correct 328 ms 62864 KB Output is correct
4 Correct 287 ms 63424 KB Output is correct
5 Correct 393 ms 65852 KB Output is correct
6 Correct 136 ms 38104 KB Output is correct
7 Correct 174 ms 38744 KB Output is correct
8 Correct 154 ms 39088 KB Output is correct
9 Correct 152 ms 39992 KB Output is correct
10 Correct 168 ms 38596 KB Output is correct
11 Correct 297 ms 64248 KB Output is correct
12 Correct 272 ms 60668 KB Output is correct
13 Correct 299 ms 60608 KB Output is correct
14 Correct 282 ms 64172 KB Output is correct
15 Correct 311 ms 62720 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 146 ms 40680 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2004 KB Output is correct
2 Correct 9 ms 1876 KB Output is correct
3 Correct 8 ms 1880 KB Output is correct
4 Correct 6 ms 2012 KB Output is correct
5 Correct 7 ms 1972 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 6 ms 1548 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 5 ms 1500 KB Output is correct
10 Correct 5 ms 1548 KB Output is correct
11 Correct 6 ms 2004 KB Output is correct
12 Correct 6 ms 1880 KB Output is correct
13 Correct 6 ms 1876 KB Output is correct
14 Correct 7 ms 2004 KB Output is correct
15 Correct 6 ms 2012 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 5 ms 1620 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2004 KB Output is correct
2 Correct 9 ms 1876 KB Output is correct
3 Correct 8 ms 1880 KB Output is correct
4 Correct 6 ms 2012 KB Output is correct
5 Correct 7 ms 1972 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 6 ms 1548 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 5 ms 1500 KB Output is correct
10 Correct 5 ms 1548 KB Output is correct
11 Correct 6 ms 2004 KB Output is correct
12 Correct 6 ms 1880 KB Output is correct
13 Correct 6 ms 1876 KB Output is correct
14 Correct 7 ms 2004 KB Output is correct
15 Correct 6 ms 2012 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 5 ms 1620 KB Output is correct
18 Correct 82 ms 4768 KB Output is correct
19 Correct 67 ms 4308 KB Output is correct
20 Correct 102 ms 4644 KB Output is correct
21 Correct 70 ms 4420 KB Output is correct
22 Correct 76 ms 4456 KB Output is correct
23 Correct 74 ms 3956 KB Output is correct
24 Correct 83 ms 4228 KB Output is correct
25 Correct 67 ms 4228 KB Output is correct
26 Correct 72 ms 4092 KB Output is correct
27 Correct 64 ms 3960 KB Output is correct
28 Correct 59 ms 3908 KB Output is correct
29 Correct 51 ms 4028 KB Output is correct
30 Correct 50 ms 4092 KB Output is correct
31 Correct 52 ms 4000 KB Output is correct
32 Correct 49 ms 4044 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 60 ms 3844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 66184 KB Output is correct
2 Correct 373 ms 64876 KB Output is correct
3 Correct 301 ms 60844 KB Output is correct
4 Correct 311 ms 60248 KB Output is correct
5 Correct 304 ms 61940 KB Output is correct
6 Correct 143 ms 38428 KB Output is correct
7 Correct 152 ms 38096 KB Output is correct
8 Correct 151 ms 38316 KB Output is correct
9 Correct 152 ms 37940 KB Output is correct
10 Correct 164 ms 41012 KB Output is correct
11 Correct 284 ms 60264 KB Output is correct
12 Correct 306 ms 65620 KB Output is correct
13 Correct 285 ms 60096 KB Output is correct
14 Correct 279 ms 61792 KB Output is correct
15 Correct 325 ms 65372 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 153 ms 38972 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 63484 KB Output is correct
2 Correct 299 ms 62584 KB Output is correct
3 Correct 328 ms 62864 KB Output is correct
4 Correct 287 ms 63424 KB Output is correct
5 Correct 393 ms 65852 KB Output is correct
6 Correct 136 ms 38104 KB Output is correct
7 Correct 174 ms 38744 KB Output is correct
8 Correct 154 ms 39088 KB Output is correct
9 Correct 152 ms 39992 KB Output is correct
10 Correct 168 ms 38596 KB Output is correct
11 Correct 297 ms 64248 KB Output is correct
12 Correct 272 ms 60668 KB Output is correct
13 Correct 299 ms 60608 KB Output is correct
14 Correct 282 ms 64172 KB Output is correct
15 Correct 311 ms 62720 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 146 ms 40680 KB Output is correct
18 Correct 6 ms 2004 KB Output is correct
19 Correct 9 ms 1876 KB Output is correct
20 Correct 8 ms 1880 KB Output is correct
21 Correct 6 ms 2012 KB Output is correct
22 Correct 7 ms 1972 KB Output is correct
23 Correct 5 ms 1620 KB Output is correct
24 Correct 6 ms 1548 KB Output is correct
25 Correct 5 ms 1620 KB Output is correct
26 Correct 5 ms 1500 KB Output is correct
27 Correct 5 ms 1548 KB Output is correct
28 Correct 6 ms 2004 KB Output is correct
29 Correct 6 ms 1880 KB Output is correct
30 Correct 6 ms 1876 KB Output is correct
31 Correct 7 ms 2004 KB Output is correct
32 Correct 6 ms 2012 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 5 ms 1620 KB Output is correct
35 Correct 82 ms 4768 KB Output is correct
36 Correct 67 ms 4308 KB Output is correct
37 Correct 102 ms 4644 KB Output is correct
38 Correct 70 ms 4420 KB Output is correct
39 Correct 76 ms 4456 KB Output is correct
40 Correct 74 ms 3956 KB Output is correct
41 Correct 83 ms 4228 KB Output is correct
42 Correct 67 ms 4228 KB Output is correct
43 Correct 72 ms 4092 KB Output is correct
44 Correct 64 ms 3960 KB Output is correct
45 Correct 59 ms 3908 KB Output is correct
46 Correct 51 ms 4028 KB Output is correct
47 Correct 50 ms 4092 KB Output is correct
48 Correct 52 ms 4000 KB Output is correct
49 Correct 49 ms 4044 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 60 ms 3844 KB Output is correct
52 Correct 333 ms 66184 KB Output is correct
53 Correct 373 ms 64876 KB Output is correct
54 Correct 301 ms 60844 KB Output is correct
55 Correct 311 ms 60248 KB Output is correct
56 Correct 304 ms 61940 KB Output is correct
57 Correct 143 ms 38428 KB Output is correct
58 Correct 152 ms 38096 KB Output is correct
59 Correct 151 ms 38316 KB Output is correct
60 Correct 152 ms 37940 KB Output is correct
61 Correct 164 ms 41012 KB Output is correct
62 Correct 284 ms 60264 KB Output is correct
63 Correct 306 ms 65620 KB Output is correct
64 Correct 285 ms 60096 KB Output is correct
65 Correct 279 ms 61792 KB Output is correct
66 Correct 325 ms 65372 KB Output is correct
67 Correct 1 ms 340 KB Output is correct
68 Correct 153 ms 38972 KB Output is correct
69 Correct 604 ms 65536 KB Output is correct
70 Correct 547 ms 68596 KB Output is correct
71 Correct 533 ms 63748 KB Output is correct
72 Correct 633 ms 66868 KB Output is correct
73 Correct 627 ms 66016 KB Output is correct
74 Correct 459 ms 45088 KB Output is correct
75 Correct 398 ms 41944 KB Output is correct
76 Correct 438 ms 45320 KB Output is correct
77 Correct 443 ms 41796 KB Output is correct
78 Correct 436 ms 42476 KB Output is correct
79 Correct 460 ms 67908 KB Output is correct
80 Correct 425 ms 63420 KB Output is correct
81 Correct 439 ms 63084 KB Output is correct
82 Correct 451 ms 66320 KB Output is correct
83 Correct 381 ms 63428 KB Output is correct
84 Correct 1 ms 340 KB Output is correct
85 Correct 291 ms 41860 KB Output is correct