oj.uz

Submission #919636

# Submission time Handle Problem Language Result Execution time Memory
919636 2024-02-01T09:35:20 Z sleepntsheep NLO (COCI18_nlo) C++17
22 / 110
 2686 ms 3160 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[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;
            }
            if(-1==zr)continue;
            _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 5 ms 2648 KB Output isn't correct
2 Correct 17 ms 2648 KB Output is correct
3 Incorrect 17 ms 2648 KB Output isn't correct
4 Incorrect 52 ms 2648 KB Output isn't correct
5 Incorrect 39 ms 2648 KB Output isn't correct
6 Incorrect 680 ms 2668 KB Output isn't correct
7 Incorrect 333 ms 2896 KB Output isn't correct
8 Incorrect 1824 ms 2920 KB Output isn't correct
9 Incorrect 799 ms 2904 KB Output isn't correct
10 Correct 2686 ms 3160 KB Output is correct