제출 #434369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434369		qwerasdfzxcl	Teams (IOI15_teams)	C++14	34 / 100	4082 ms	313096 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;
struct Node{
    int n, lazy, org;
    Node* nxt[4]; ///ll, lr, rl, rr
    Node(){n = lazy = org = 0; fill(nxt, nxt+4, nullptr);}
    ~Node(){for (int i=0;i<4;i++) if (nxt[i]) delete nxt[i];}
    void propagate(){
        if (lazy==1) n = 0;
        if (lazy==2) n = org;
        if (lazy){
            for (int i=0;i<4;i++) if (nxt[i]) nxt[i]->lazy = lazy;
        }
        lazy = 0;
    }
    void update1(int lx, int rx, int ly, int ry, int sx, int ex, int sy, int ey, int val){
        propagate();
        if (rx<sx || ex<lx) return;
        if (ry<sy || ey<ly) return;
        if (sx<=lx && rx<=ex && sy<=ly && ry<=ey){
            lazy = val; propagate();
            return;
        }
        int mx = (lx+rx)>>1, my = (ly+ry)>>1;
        if (nxt[0]) nxt[0]->update1(lx, mx, ly, my, sx, ex, sy, ey, val);
        if (nxt[1]) nxt[1]->update1(lx, mx, my+1, ry, sx, ex, sy, ey, val);
        if (nxt[2]) nxt[2]->update1(mx+1, rx, ly, my, sx, ex, sy, ey, val);
        if (nxt[3]) nxt[3]->update1(mx+1, rx, my+1, ry, sx, ex, sy, ey, val);
        n = 0;
        for (int i=0;i<4;i++) if (nxt[i]) n += nxt[i]->n;
    }
    void update2(int lx, int rx, int ly, int ry, int x, int y){
        if (lx==rx && ly==ry) {n++, org++; return;}
        int mx = (lx+rx)>>1, my = (ly+ry)>>1;
        if (lx<=x && x<=mx && ly<=y && y<=my){
            if (!nxt[0]) nxt[0] = new Node();
            nxt[0]->update2(lx, mx, ly, my, x, y);
        }
        if (lx<=x && x<=mx && my+1<=y && y<=ry){
            if (!nxt[1]) nxt[1] = new Node();
            nxt[1]->update2(lx, mx, my+1, ry, x, y);
        }
        if (mx+1<=x && x<=rx && ly<=y && y<=my){
            if (!nxt[2]) nxt[2] = new Node();
            nxt[2]->update2(mx+1, rx, ly, my, x, y);
        }
        if (mx+1<=x && x<=rx && my+1<=y && y<=ry){
            if (!nxt[3]) nxt[3] = new Node();
            nxt[3]->update2(mx+1, rx, my+1, ry, x, y);
        }
        n = 0;
        for (int i=0;i<4;i++) if (nxt[i]) n += nxt[i]->n;
        org = n;
    }
    void update3(int lx, int rx, int ly, int ry, int x, int y, int val){
        propagate();
        if (lx==rx && ly==ry) {n -= val; return;}
        int mx = (lx+rx)>>1, my = (ly+ry)>>1;
        if (lx<=x && x<=mx && ly<=y && y<=my){
            assert(nxt[0]);
            nxt[0]->update3(lx, mx, ly, my, x, y, val);
        }
        if (lx<=x && x<=mx && my+1<=y && y<=ry){
            assert(nxt[1]);
            nxt[1]->update3(lx, mx, my+1, ry, x, y, val);
        }
        if (mx+1<=x && x<=rx && ly<=y && y<=my){
            assert(nxt[2]);
            nxt[2]->update3(mx+1, rx, ly, my, x, y, val);
        }
        if (mx+1<=x && x<=rx && my+1<=y && y<=ry){
            assert(nxt[3]);
            nxt[3]->update3(mx+1, rx, my+1, ry, x, y, val);
        }
        n = 0;
        for (int i=0;i<4;i++) if (nxt[i]) n += nxt[i]->n;
    }
    int query(int lx, int rx, int ly, int ry, int sx, int ex, int sy, int ey){
        //printf("Query: %d %d %d %d %d %d %d %d\n%d %d\n", lx, rx, ly, ry, sx, ex, sy, ey, n, org);
        propagate();
        if (rx<sx || ex<lx) return 0;
        if (ry<sy || ey<ly) return 0;
        if (sx<=lx && rx<=ex && sy<=ly && ry<=ey) return n;
        int mx = (lx+rx)>>1, my = (ly+ry)>>1;
        int ret = 0;
        if (nxt[0]) ret += nxt[0]->query(lx, mx, ly, my, sx, ex, sy, ey);
        if (nxt[1]) ret += nxt[1]->query(lx, mx, my+1, ry, sx, ex, sy, ey);
        if (nxt[2]) ret += nxt[2]->query(mx+1, rx, ly, my, sx, ex, sy, ey);
        if (nxt[3]) ret += nxt[3]->query(mx+1, rx, my+1, ry, sx, ex, sy, ey);
        return ret;
    }
};

Node* tree;
int N;

void init(int n, int A[], int B[]) {
    N = n;
    tree = new Node();
    for (int i=0;i<n;i++){
        tree->update2(1, n, 1, n, A[i], B[i]);
    }
}

int can(int M, int K[]) {
    int S = 0;
    for (int i=0;i<M;i++) S += K[i];
    if (S>N) return 0;
    sort(K, K+M, greater<int>());
    tree->update1(1, N, 1, N, 1, N, 1, N, 2);
    for (int i=0;i<M;i++){
        //printf("%d: ", i);
        int chk = tree->query(1, N, 1, N, 1, K[i], K[i], N);
        if (chk<K[i]) return 0;
        int l = 1, r = K[i]+1, idx = 1e9;
        //printf("%d ", tree->query(1, N, 1, N, 2, K[i], K[i], N));
        while(l<r){
            int m = (l+r)>>1;
            if (tree->query(1, N, 1, N, m, K[i], K[i], N)>=K[i]) l = m+1, idx = m;
            else r = m;
        }
        assert(idx!=1e9);
        int tmp = K[i];
        if (idx+1<=K[i]) tmp -= tree->query(1, N, 1, N, idx+1, K[i], K[i], N);
        if (idx+1<=K[i]) tree->update1(1, N, 1, N, idx+1, K[i], K[i], N, 1);
        l = K[i], r = N+1;
        //printf("%d ", idx);
        int idx2 = 1e9;
        while(l<r){
            int m = (l+r)>>1;
            if (tree->query(1, N, 1, N, idx, idx, m, N)>=tmp) l = m+1, idx2 = m;
            else r = m;
        }
        assert(idx2!=1e9);
        //printf("%d\n", idx2);
        int tmp2 = tmp;
        if (idx2+1<=N) tmp2 -= tree->query(1, N, 1, N, idx, idx, idx2+1, N);
        if (idx2+1<=N) tree->update1(1, N, 1, N, idx, idx, idx2+1, N, 1);
        tree->update3(1, N, 1, N, idx, idx2, tmp2);
    }
    return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23