Submission #333540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333540	2020-12-06T23:32:58 Z	doowey	NLO (COCI18_nlo)	C++14	88 / 110	3000 ms	8172 KB

nlo

#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<<1].lazy=T[node].lazy;
        T[node<<1|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;
    int sol = 0;
    if(mid >= tl) sol += get(node<<1,cl,mid,tl,tr);
    if(cl <= tr) sol += get(node<<1|1,mid+1,cr,tl,tr);
    return sol;
}

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<<1,cl,mid,tl,tr,type);
    update(node<<1|1,mid+1,cr,tl,tr,type);
    T[node].cnt = T[node<<1].cnt + T[node<<1|1].cnt;
}

bool active[K];

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    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};
    }
    ll soln = 0;
    int id;
    int delta;
    vector<int> sg;
    for(int row = 1; row <= n; row ++ ){
        for(auto xx : add[row]) active[xx]=true;
        for(auto xx : rem[row]) active[xx]=false;
        update(1, 1, m, 1, m, 1);
        for(int i = k; i >= 1 ; i -- ){
            if(!active[i]) continue;
            delta = sqrt(sq(r[i])-sq(row-x[i]));
            xl[i]=y[i]-delta;
            xr[i]=y[i]+delta;
            soln += get(1, 1, m, xl[i], xr[i]) * 1ll * (k-i);
            update(1, 1, m, xl[i], xr[i], 0);
        }
        soln += T[1].cnt * 1ll * k;
    }
    cout << soln << "\n";
    return 0;
}

Compilation message

nlo.cpp: In function 'int main()':
nlo.cpp:88:9: warning: unused variable 'id' [-Wunused-variable]
   88 |     int id;
      |         ^~

Subtask #1

88.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	5100 KB	Output is correct
2	Correct	29 ms	5100 KB	Output is correct
3	Correct	27 ms	5100 KB	Output is correct
4	Correct	210 ms	5376 KB	Output is correct
5	Correct	213 ms	6508 KB	Output is correct
6	Correct	1582 ms	6252 KB	Output is correct
7	Correct	672 ms	7276 KB	Output is correct
8	Execution timed out	3069 ms	7660 KB	Time limit exceeded
9	Correct	1264 ms	7660 KB	Output is correct
10	Execution timed out	3027 ms	8172 KB	Time limit exceeded