oj.uz

Submission #983932

# Submission time Handle Problem Language Result Execution time Memory
983932 2024-05-16T08:12:44 Z WongYiKai Seats (IOI18_seats) C++14
5 / 100
 4000 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,*root4;


ll h,w,n;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h = H;
	w = W;
	
	n = h*w;
    root = new node(0,1000100);
    root2 = new node(0,1000100);
    root3 = new node(0,1000100);
	//root -> row
	//root2 -> col
	//root3 -> yes/no
	int high1=0,high2=0,low1=2000000,low2=2000000;
	for (int i=0;i<n;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";
	}
}

ll left2,right2,top2,bottom2;
ll temp;
ll r,c,ind,ind2;
int swap_seats(int a, int b) {
    
    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 = root->range_sum(a,a);
    c = root2->range_sum(a,a);
    root->set(a,a,root->range_sum(b,b));
    root->set(b,b,r);
    root2->set(a,a,root2->range_sum(b,b));
    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 9 ms 348 KB Output is correct
2 Correct 12 ms 604 KB Output is correct
3 Correct 10 ms 856 KB Output is correct
4 Correct 10 ms 604 KB Output is correct
5 Correct 47 ms 604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 10 ms 604 KB Output is correct
8 Correct 14 ms 604 KB Output is correct
9 Correct 15 ms 604 KB Output is correct
10 Correct 10 ms 600 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Correct 42 ms 596 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 12 ms 604 KB Output is correct
3 Correct 10 ms 856 KB Output is correct
4 Correct 10 ms 604 KB Output is correct
5 Correct 47 ms 604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 10 ms 604 KB Output is correct
8 Correct 14 ms 604 KB Output is correct
9 Correct 15 ms 604 KB Output is correct
10 Correct 10 ms 600 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Correct 42 ms 596 KB Output is correct
13 Correct 23 ms 4176 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 20 ms 4180 KB Output is correct
16 Execution timed out 4065 ms 4444 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 660 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 19 ms 3928 KB Output is correct
2 Correct 84 ms 28548 KB Output is correct
3 Runtime error 666 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 79 ms 1232 KB Output is correct
2 Correct 93 ms 2060 KB Output is correct
3 Correct 414 ms 2120 KB Output is correct
4 Correct 2677 ms 2688 KB Output is correct
5 Correct 140 ms 6000 KB Output is correct
6 Runtime error 633 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 9 ms 348 KB Output is correct
2 Correct 12 ms 604 KB Output is correct
3 Correct 10 ms 856 KB Output is correct
4 Correct 10 ms 604 KB Output is correct
5 Correct 47 ms 604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 10 ms 604 KB Output is correct
8 Correct 14 ms 604 KB Output is correct
9 Correct 15 ms 604 KB Output is correct
10 Correct 10 ms 600 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Correct 42 ms 596 KB Output is correct
13 Correct 23 ms 4176 KB Output is correct
14 Correct 20 ms 4188 KB Output is correct
15 Correct 20 ms 4180 KB Output is correct
16 Execution timed out 4065 ms 4444 KB Time limit exceeded
17 Halted 0 ms 0 KB -