oj.uz

Submission #919633

# Submission time Handle Problem Language Result Execution time Memory
919633 2024-02-01T09:33:45 Z sleepntsheep NLO (COCI18_nlo) C++17
22 / 110
 2682 ms 9308 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 200005

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,N<<4);
    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[x,y,r2]=a[j];
            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;
            }
            assert(zr+1);
            _upd(0,1,m,zl,zr,left);
        }
        an+=_qry(0,1,m,1,m);
    }
    cout<<an;


    return 0;
}

Subtask #1
22.0 / 110.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4696 KB Output isn't correct
2 Correct 18 ms 4696 KB Output is correct
3 Runtime error 5 ms 9308 KB Execution killed with signal 6
4 Incorrect 60 ms 4948 KB Output isn't correct
5 Incorrect 39 ms 4696 KB Output isn't correct
6 Runtime error 5 ms 9304 KB Execution killed with signal 6
7 Incorrect 327 ms 4736 KB Output isn't correct
8 Incorrect 1827 ms 4944 KB Output isn't correct
9 Runtime error 6 ms 9240 KB Execution killed with signal 6
10 Correct 2682 ms 4720 KB Output is correct