oj.uz

Submission #634571

# Submission time Handle Problem Language Result Execution time Memory
634571 2022-08-24T15:06:11 Z yunny_world NLO (COCI18_nlo) C++14
110 / 110
 770 ms 332 KB 
#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];
ll ans;

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

    ans=n*m*k;

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

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

            if(r*r-(y-i)*(y-i)<0) continue;

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

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

        set<ll> s;
        for(ll 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 만큼의 풀이 자람
즉, 각 위치에 대해 가장 마지막으로 적용된 쿼리만 알면 된다.

https://oj.uz/submission/230502
*/

Compilation message

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

Subtask #1
110.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 11 ms 332 KB Output is correct
3 Correct 6 ms 212 KB Output is correct
4 Correct 50 ms 324 KB Output is correct
5 Correct 33 ms 296 KB Output is correct
6 Correct 318 ms 308 KB Output is correct
7 Correct 99 ms 212 KB Output is correct
8 Correct 585 ms 320 KB Output is correct
9 Correct 171 ms 312 KB Output is correct
10 Correct 770 ms 312 KB Output is correct