Submission #634563

#	Time	Username	Problem	Language	Result	Execution time	Memory
634563		yunny_world	NLO (COCI18_nlo)	C++14	44 / 110	834 ms	328 KiB

nlo

#include <bits/stdc++.h>
#define ll long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define X first
#define Y second
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

ll n, m, k;
tuple<ll, ll, ll> query[105];
int ans;

void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        ll x, y, r; cin>>x>>y>>r;
        query[i]=tie(x, y, r);
    }

    ans=n*m*k;

    for(int i=1;i<=m;i++)
    {
        vector<pll> v;

        for(int j=1;j<=k;j++)
        {
            ll x, y, r;
            tie(x, y, r)=query[j];

            ll s=x-floor(sqrt(r*r-(y-i)*(y-i)));
            ll e=x+floor(sqrt(r*r-(y-i)*(y-i)));
            if(s>0 && e>0 && s<=e)
            {
                v.push_back({s, j});
                v.push_back({e+1, -j});
            }
        }

        sort(v.begin(), v.end());

        set<ll> s;
        for(int j=0;j<v.size();j++)
        {
            //cout<<v[j].X<<' '<<v[j].Y<<'\n';
            if(!s.empty()) ans-=(*s.rbegin() * (v[j].X-v[j-1].X));
            if(v[j].Y<0) s.erase(-v[j].Y);
            else s.insert(v[j].Y);
        }
        //cout<<'\n';
    }
    cout<<ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
    return 0;
}
/*
어떤 위치에 q번째 쿼리가 마지막으로 적용 됨 -> k-q 만큼의 풀이 자람
즉, 각 위치에 대해 가장 마지막으로 적용된 쿼리만 알면 된다.
*/

Compilation message (stderr)

nlo.cpp: In function 'void solve()':
nlo.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int j=0;j<v.size();j++)
      |                     ~^~~~~~~~~

• Subtask 1: 44 / 110