oj.uz

Submission #983936

# Submission time Handle Problem Language Result Execution time Memory
983936 2024-05-16T08:17:09 Z WongYiKai Seats (IOI18_seats) C++14
11 / 100
 3726 ms 262144 KB 
#include "seats.h"



#include <bits/stdc++.h>
using namespace std;

typedef int ll;

struct node {
    int s, e;
    ll mn, mx, sum;
    bool lset;
    ll add_val, set_val;
    node *l, *r;
    node (int _s, int _e, int A[] = NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL) {
        if (A == NULL) return;
        if (s == e) mn = mx = sum = A[s];
        else {
            l = new node(s, (s+e)>>1, A), r = new node((s+e+2)>>1, e, A);
            combine();
        }
    }
    void create_children() {
        if (s == e) return;
        if (l != NULL) return;
        int m = (s+e)>>1;
        l = new node(s, m);
        r = new node(m+1, e);
    }
    void self_set(ll v) {
        lset = 1;
        mn = mx = set_val = v;
        sum = v * (e-s+1);
        add_val = 0;
    }
    void self_add(ll v) {
        if (lset) { self_set(v + set_val); return; }
        mn += v, mx += v, add_val += v;
        sum += v*(e-s+1);
    }
    void lazy_propagate() {
        if (s == e) return;
        if (lset) {
            l->self_set(set_val), r->self_set(set_val);
            lset = set_val = 0;
        }   
        if (add_val != 0) {
            l->self_add(add_val), r->self_add(add_val);
            add_val = 0;
        }
    }
    void combine() {
        if (l == NULL) return;
        sum = l->sum + r->sum;
        mn = min(l->mn, r->mn);
        mx = max(l->mx, r->mx);
    }
    void add(int x, int y, ll v) {
        if (s == x && e == y) { self_add(v); return; }
        int m = (s+e)>>1;
        create_children(); lazy_propagate();
        if (x <= m) l->add(x, min(y, m), v);
        if (y > m) r->add(max(x, m+1), y, v);
        combine();
    }
    void set(int x, int y, ll v) {
        if (s == x && e == y) { self_set(v); return; }
        int m = (s+e)>>1;
        create_children(); lazy_propagate();
        if (x <= m) l->set(x, min(y, m), v);
        if (y > m) r->set(max(x, m+1), y, v);
        combine();
    }
    ll range_sum(int x, int y) {
        if (s == x && e == y) return sum;
        if (l == NULL || lset) return (sum / (e-s+1)) * (y-x+1);
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_sum(x, y);
        if (x > m) return r->range_sum(x, y);
        return l->range_sum(x, m) + r->range_sum(m+1, y);
    }
    ll range_min(int x, int y) {
        if (s == x && e == y) return mn;
        if (l == NULL || lset) return mn;
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_min(x, y);
        if (x > m) return r->range_min(x, y);
        return min(l->range_min(x, m), r->range_min(m+1, y));
    }
    ll range_max(int x, int y) {
        if (s == x && e == y) return mx;
        if (l == NULL || lset) return mx;
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_max(x, y);
        if (x > m) return r->range_max(x, y);
        return max(l->range_max(x, m), r->range_max(m+1, y));
    }
    ~node() {
        if (l != NULL) delete l;
        if (r != NULL) delete r;
    }
} *root,*root2,*root3;


ll h,w,n;
vector<ll> r2,c2;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h = H;
	w = W;
	
	n = h*w;
	r2 = R;
	c2 = C;
    root = new node(0,n+5);
    root2 = new node(0,n+5);
    root3 = new node(0,n+5);
	//root -> row
	//root2 -> col
	//root3 -> yes/no
	int high1=0,high2=0,low1=2000000,low2=2000000;
	for (int i=0;i<n;i++){
        r2[i] = R[i];
      	c2[i] = C[i];
		root->set(i,i,R[i]);
		root2->set(i,i,C[i]);
		
		low2 = min(low2,C[i]); //left
		low1 = min(low1,R[i]); //top
		high2 = max(high2,C[i]); //right
		high1 = max(high1,R[i]); //bottom
		ll siz = (high2-low2+1)*(high1-low1+1);
		if (siz==i+1) {
		    root3->set(i,i,1);
		}
		//cout << root3->range_sum(i,i) << "\n";
	}
}


int swap_seats(int a, int b) {
    ll left2,right2,top2,bottom2;
    ll temp;
    ll r,c,ind,ind2;
    
    if (a>b){
        temp=a;
        a=b;
        b=temp;
    }
    //everything >=b doesnt change
    //everything <a doesnt change
    //everything between them wont work anymore
    root3->set(a,b-1,0);
    r = r2[a];
    c = c2[a];
    r2[a] = r2[b];
    c2[a] = c2[b];
    r2[b] = r;
    c2[b] = c;
    root->set(a,a,r2[a]);
    root->set(b,b,r);
    root2->set(a,a,c2[a]);
    root2->set(b,b,c);
    ind=a;
    while (ind<b){
        if (ind==0){
            root3->set(0,0,1);
            ind=1;
            continue;
        }
        left2=root2->range_min(0,ind);
		right2=root2->range_max(0,ind);
		top2=root->range_min(0,ind);
		bottom2=root->range_max(0,ind);
		ind2 = (right2-left2+1)*(bottom2-top2+1)-1;
		//cout << ind << " " << ind2 << "\n";
		if (ind2==ind) {
		    root3->set(ind,ind,1);
		    ind = ind2+1;
		}
		else ind=ind2;
    }
    return root3->range_sum(0,n-1);
}

Compilation message

seats.cpp: In member function 'void node::lazy_propagate()':
seats.cpp:46:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |             lset = set_val = 0;
      |                    ~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 532 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 16 ms 540 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 532 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 16 ms 540 KB Output is correct
13 Correct 16 ms 4436 KB Output is correct
14 Correct 17 ms 4184 KB Output is correct
15 Correct 16 ms 4188 KB Output is correct
16 Correct 3726 ms 4444 KB Output is correct
17 Correct 22 ms 4444 KB Output is correct
18 Correct 124 ms 4136 KB Output is correct
19 Correct 747 ms 4248 KB Output is correct
20 Correct 3262 ms 4624 KB Output is correct
21 Correct 3178 ms 4624 KB Output is correct
22 Correct 2246 ms 4696 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 680 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3928 KB Output is correct
2 Correct 74 ms 28020 KB Output is correct
3 Runtime error 693 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1492 KB Output is correct
2 Correct 30 ms 1228 KB Output is correct
3 Correct 159 ms 1368 KB Output is correct
4 Correct 1772 ms 2272 KB Output is correct
5 Correct 101 ms 5328 KB Output is correct
6 Runtime error 672 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 532 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 16 ms 540 KB Output is correct
13 Correct 16 ms 4436 KB Output is correct
14 Correct 17 ms 4184 KB Output is correct
15 Correct 16 ms 4188 KB Output is correct
16 Correct 3726 ms 4444 KB Output is correct
17 Correct 22 ms 4444 KB Output is correct
18 Correct 124 ms 4136 KB Output is correct
19 Correct 747 ms 4248 KB Output is correct
20 Correct 3262 ms 4624 KB Output is correct
21 Correct 3178 ms 4624 KB Output is correct
22 Correct 2246 ms 4696 KB Output is correct
23 Runtime error 680 ms 262144 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -