oj.uz

Submission #919638

# Submission time Handle Problem Language Result Execution time Memory
919638 2024-02-01T09:38:14 Z sleepntsheep NLO (COCI18_nlo) C++17
110 / 110
 2631 ms 3276 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 100005

int n, m, k;


int t[N<<2], lz[N<<2];

void _push(int v, int l, int r)
{
    if (lz[v] != -1)
    {
        t[v] = (r-l+1ll)*lz[v];
        if(l^r)lz[2*v+1]=lz[2*v+2]=lz[v];
        lz[v] = -1;
    }
}

void _upd(int v, int l, int r, int x, int y, int k)
{
    _push(v, l, r);
    if (r < x or y < l) return;
    if (x <= l and r <= y)
    {
        lz[v] = k;
        _push(v, l, r);
        return;
    }
    _upd(2*v+1,l,(l+r)/2,x,y,k);
    _upd(2*v+2,(l+r)/2+1,r,x,y,k);
    t[v]=t[2*v+1]+t[2*v+2];
}

int _qry(int v, int l, int r, int x, int y)
{
    _push(v,l,r);
    if(r<x or y<l)return 0;
    if(x<=l and r<=y)return t[v];
    return _qry(2*v+2,(l+r)/2+1,r,x,y)+_qry(2*v+1,l,(l+r)/2,x,y);
}

i64 a[101][3],an;

i64 norm(i64 x, i64 y){return x*x+y*y;}

int main()
{
    memset(lz,-1,sizeof lz);
    ShinLena;
    cin >> n >> m >> k;
    for (int i=1;i<=k;++i)cin>>a[i][0]>>a[i][1]>>a[i][2];

    for(int i=1;i<=n;++i)
    {
        _upd(0,1,m,1,m,k);
        for (int j=1;j<=k;++j)
        {
            auto[y,x,r2]=a[j];
            if(abs(y-i)>r2)continue;
            r2 *=r2;
            int left=k-j;
            int zl=-1,zr=-1;
            int l=1,r=x;
            while(l<=r)
            {
                auto m=(l+r)/2;
                if(norm(m-x,i-y) <= r2) r=m-1,zl=m;
                else l=m+1;
            }
            if(-1==zl)continue;
            l=x,r=m;
            while(l<=r)
            {
                auto m=(l+r)/2;
                if(norm(m-x,i-y)<=r2)l=m+1,zr=m; else r=m-1;
            }
            if(-1==zr)continue;
            _upd(0,1,::m,zl,zr,left);
        }
        an+=_qry(0,1,m,1,m);
    }
    cout<<an;


    return 0;
}

Subtask #1
110.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Correct 16 ms 2648 KB Output is correct
3 Correct 15 ms 2648 KB Output is correct
4 Correct 125 ms 2672 KB Output is correct
5 Correct 119 ms 2672 KB Output is correct
6 Correct 888 ms 2896 KB Output is correct
7 Correct 367 ms 3244 KB Output is correct
8 Correct 1921 ms 3172 KB Output is correct
9 Correct 698 ms 3276 KB Output is correct
10 Correct 2631 ms 3024 KB Output is correct