답안 #333528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333528 2020-12-06T20:51:30 Z doowey NLO (COCI18_nlo) C++14
88 / 110
3000 ms 8172 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
const int K = 105;
int x[K], y[K], r[K];
int xl[K], xr[K];
vector<int> add[N];
vector<int> rem[N];

ll sq(ll x){
    return x * 1ll * x;
}

struct Node{
    int cnt;
    int lazy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    if(T[node].lazy == -1) return;
    if(T[node].lazy == 0)
        T[node].cnt=0;
    else
        T[node].cnt=(cr-cl+1);
    if(cl != cr){
        T[node*2].lazy=T[node].lazy;
        T[node*2+1].lazy=T[node].lazy;
    }
    T[node].lazy = -1;
}

int get(int node, int cl, int cr, int tl, int tr){
    push(node,cl,cr);
    if(cr < tl || cl > tr) return 0;
    if(cl >= tl && cr <= tr){
        return T[node].cnt;
    }
    int mid = (cl + cr) / 2;
    return get(node*2,cl,mid,tl,tr)+get(node*2+1,mid+1,cr,tl,tr);
}

void update(int node, int cl, int cr, int tl, int tr, int type){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lazy=type;
        push(node,cl,cr);
        return;
    }
    int mid = (cl + cr) / 2;
    update(node*2,cl,mid,tl,tr,type);
    update(node*2+1,mid+1,cr,tl,tr,type);
    T[node].cnt = T[node*2].cnt + T[node*2+1].cnt;
}

int main(){
    fastIO;
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= k ; i ++ ){
        cin >> x[i] >> y[i] >> r[i];
        add[x[i]-r[i]].push_back(i);
        xl[i]=xr[i]=y[i];
        rem[x[i]+r[i]+1].push_back(i);
    }
    for(int i = 1; i <= m * 4 + 100; i ++ ){
        T[i] = {0,-1};
    }
    set<int> active;
    ll soln = 0;
    int id;
    for(int i = 1; i <= n; i ++ ){
        for(auto xx : add[i]){
            active.insert(xx);
        }
        for(auto xx : rem[i]){
            active.erase(xx);
        }
        for(auto xx : active){
            if(i <= x[xx]){
                while(sq((xl[xx]-1)-y[xx]) + sq(i-x[xx]) <= sq(r[xx])){
                    xl[xx]--;
                    xr[xx]++;
                }
            }
            else{
                while(sq(xl[xx]-y[xx])+sq(i-x[xx]) > sq(r[xx])){
                    xl[xx]++;
                    xr[xx]--;
                }
            }
        }
        auto it = active.end();
        update(1, 1, m, 1, m, 1);
        while(it != active.begin()){
            it -- ;
            id = *it;
            soln += (k-id) * 1ll * get(1, 1, m, xl[id], xr[id]);
            update(1, 1, m, xl[id], xr[id], 0);
        }
        soln += k * 1ll * T[1].cnt;
    }
    cout << soln << "\n";
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5100 KB Output is correct
2 Correct 32 ms 5100 KB Output is correct
3 Correct 28 ms 5248 KB Output is correct
4 Correct 224 ms 5484 KB Output is correct
5 Correct 224 ms 6380 KB Output is correct
6 Correct 1659 ms 6144 KB Output is correct
7 Correct 695 ms 7148 KB Output is correct
8 Execution timed out 3082 ms 7732 KB Time limit exceeded
9 Correct 1319 ms 7660 KB Output is correct
10 Execution timed out 3100 ms 8172 KB Time limit exceeded