oj.uz

Submission #880492

# Submission time Handle Problem Language Result Execution time Memory
880492 2023-11-29T14:17:42 Z dubabuba Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 95696 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    typedef vector<int> vi;
     
    const int mxl = 25;
    const int mxn = 2e5 + 10;
    vector<vi> sus(mxl, vi (mxn));
    vector<vi> tmp(mxl, vi (mxn));
    int a[mxn], n, m;
     
    struct con {
    	int ans, max;
    	con() {ans = max = 0;}
    } str[mxn * 4];
     
    void ono_max(int &MAX, int CMP) { if(MAX < CMP) MAX = CMP;}
    void ono_min(int &MIN, int CMP) { if(MIN > CMP) MIN = CMP;}
     
    void build(int idx, int lvl, int tl, int tr) {
    	if(tl == tr) {
//    		cout << tl << ": " << a[tl] << '\n';
    		sus[lvl][tl] = a[tl];
    		str[idx].max = a[tl];
    		str[idx].ans = 0;
    		return;
    	}
     
    	int tm = (tl + tr) / 2;
    	build(idx * 2 + 1, lvl + 1, tl, tm);
    	build(idx * 2 + 2, lvl + 1, tm + 1, tr);
     
    	int L = tl, R = tm + 1, i = tl;
    	while(1) {
    		if(L == tm + 1 && R == tr + 1) break;
    		if(L == tm + 1) {
    			sus[lvl][i] = sus[lvl + 1][R];
    			i++, R++;
    			continue;
    		}
    		if(R == tr + 1) {
    			sus[lvl][i] = sus[lvl + 1][L];
    			i++, L++;
    			continue;
    		}
     
    		if(sus[lvl + 1][L] <= sus[lvl + 1][R]) {
    			sus[lvl][i] = sus[lvl + 1][L];
    			L++, i++;
    		}
    		else {
    			sus[lvl][i] = sus[lvl + 1][R];
    			ono_max(str[idx].ans, str[idx * 2 + 1].max + sus[lvl][i]);
    			R++, i++;
    		}
    	}
     
    	ono_max(str[idx].max, str[idx * 2 + 1].max);
    	ono_max(str[idx].max, str[idx * 2 + 2].max);
     
    	ono_max(str[idx].ans, str[idx * 2 + 1].ans);
    	ono_max(str[idx].ans, str[idx * 2 + 2].ans);
     
    	// cout << tl << ' ' << tr << ":\n";
    	// for(int i = tl; i <= tr; i++)
    	// 	cout << sus[lvl][i] << ' ';
    	// cout << "- " << str[idx].max << ' ' << str[idx].ans << '\n';
    }
     
    set<int> s;
    con query(int idx, int lvl, int tl, int tr, int l, int r) {
    	if(tl == l && r == tr) {
    		if(s.find(lvl) == s.end()) {
    			swap(sus[lvl], tmp[lvl]);
    			s.insert(lvl);
    		}
    		return str[idx];
    	}
    	int tm = (tl + tr) / 2;
    	if(r <= tm) return query(idx * 2 + 1, lvl + 1, tl, tm, l, r);
    	if(tm < l) return query(idx * 2 + 2, lvl + 1, tm + 1, tr, l, r);
     
    	con L_qr = query(idx * 2 + 1, lvl + 1, tl, tm, l, tm);
    	con R_qr = query(idx * 2 + 2, lvl + 1, tm + 1, tr, tm + 1, r);
    	con ret;
     
    	int L = l, R = tm + 1, i = l;
    	while(1) {
    		if(L == tm + 1 && R == tr + 1) break;
    		if(L == tm + 1) {
    			tmp[lvl][i] = tmp[lvl + 1][R];
    			i++, R++;
    			continue;
    		}
    		if(R == tr + 1) {
    			tmp[lvl][i] = tmp[lvl + 1][L];
    			i++, L++;
    			continue;
    		}
     
    		if(tmp[lvl + 1][L] <= tmp[lvl + 1][R]) {
    			tmp[lvl][i] = tmp[lvl + 1][L];
    			L++, i++;
    		}
    		else {
    			tmp[lvl][i] = tmp[lvl + 1][R];
    			ono_max(ret.ans, L_qr.max + tmp[lvl][i]);
    			R++, i++;
    		}
    	}
     
    	ono_max(ret.ans, L_qr.ans);
    	ono_max(ret.ans, R_qr.ans);
     
    	ono_max(ret.max, L_qr.max);
    	ono_max(ret.max, R_qr.max);
    	return ret;
    }
     
    int main() {
    	cin >> n >> m;
    	for(int i = 1; i <= n; i++)
    		cin >> a[i];
     
    	build(0, 0, 1, n);
    	// for(int i = 1; i <= n; i++)
    	// 	cout << sus[0][i] << ' ';
     
    	while(m--) {
    		int l, r, k;
    		cin >> l >> r >> k;
     
    		for(int i : s)
    			swap(sus[i], tmp[i]);
    		s.clear();
     
    		con q = query(0, 0, 1, n, l, r);
    		cout << (q.ans <= k) << '\n';
    	}
    	return 0;
    }

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 46656 KB Output is correct
2 Correct 19 ms 46668 KB Output is correct
3 Incorrect 20 ms 46668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 46656 KB Output is correct
2 Correct 19 ms 46668 KB Output is correct
3 Incorrect 20 ms 46668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 95696 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 47596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 46656 KB Output is correct
2 Correct 19 ms 46668 KB Output is correct
3 Incorrect 20 ms 46668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 46656 KB Output is correct
2 Correct 19 ms 46668 KB Output is correct
3 Incorrect 20 ms 46668 KB Output isn't correct
4 Halted 0 ms 0 KB -