oj.uz

답안 #983943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983943 2024-05-16T08:20:19 Z WongYiKai 자리 배치 (IOI18_seats) C++14
11 / 100
 3748 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;
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);
    root4 = 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";
	}
	R.clear();
	C.clear();
}


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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 472 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 18 ms 600 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 564 KB Output is correct
8 Correct 6 ms 600 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 600 KB Output is correct
12 Correct 16 ms 564 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 472 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 18 ms 600 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 564 KB Output is correct
8 Correct 6 ms 600 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 600 KB Output is correct
12 Correct 16 ms 564 KB Output is correct
13 Correct 16 ms 4188 KB Output is correct
14 Correct 16 ms 4188 KB Output is correct
15 Correct 16 ms 4188 KB Output is correct
16 Correct 3748 ms 4436 KB Output is correct
17 Correct 19 ms 4188 KB Output is correct
18 Correct 115 ms 3876 KB Output is correct
19 Correct 806 ms 3992 KB Output is correct
20 Correct 3303 ms 4444 KB Output is correct
21 Correct 3220 ms 4444 KB Output is correct
22 Correct 2297 ms 4436 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 631 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3928 KB Output is correct
2 Correct 73 ms 27828 KB Output is correct
3 Runtime error 629 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1496 KB Output is correct
2 Correct 26 ms 1440 KB Output is correct
3 Correct 167 ms 1416 KB Output is correct
4 Correct 1811 ms 1784 KB Output is correct
5 Correct 99 ms 5328 KB Output is correct
6 Runtime error 572 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 472 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 18 ms 600 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 564 KB Output is correct
8 Correct 6 ms 600 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 600 KB Output is correct
12 Correct 16 ms 564 KB Output is correct
13 Correct 16 ms 4188 KB Output is correct
14 Correct 16 ms 4188 KB Output is correct
15 Correct 16 ms 4188 KB Output is correct
16 Correct 3748 ms 4436 KB Output is correct
17 Correct 19 ms 4188 KB Output is correct
18 Correct 115 ms 3876 KB Output is correct
19 Correct 806 ms 3992 KB Output is correct
20 Correct 3303 ms 4444 KB Output is correct
21 Correct 3220 ms 4444 KB Output is correct
22 Correct 2297 ms 4436 KB Output is correct
23 Runtime error 631 ms 262144 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -