# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
957604 |
2024-04-04T05:11:16 Z |
onlk97 |
Aliens (IOI16_aliens) |
C++14 |
|
2 ms |
600 KB |
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector <pair <__int128,__int128> > v;
struct Line{
mutable __int128 m,c,p;
bool operator<(const Line&o) const {
return m<o.m;
};
bool operator<(__int128 val) const {
return p<val;
};
};
struct LineContainer:multiset <Line,less<> > {
const __int128 inf=1e36;
__int128 div(__int128 a,__int128 b){
return a/b-((a^b)<0&&a%b);
}
bool intrs(iterator a,iterator b){
if (b==end()) return a->p=inf,0;
if (a->m==b->m) a->p=(a->c>b->c?inf:-inf);
else a->p=div(b->c-a->c,a->m-b->m);
return a->p>=b->p;
}
void addline(__int128 m,__int128 c){
auto z=insert({-m,-c,0});
auto a=z++;
auto b=a;
while (intrs(b,z)) z=erase(z);
if (a!=begin()&&intrs(--a,b)) intrs(a,b=erase(b));
while ((b=a)!=begin()&&(--a)->p>=b->p) intrs(a,erase(b));
}
__int128 query(__int128 val){
auto l=*lower_bound(val);
return -l.m*val-l.c;
}
};
const __int128 C=2e5;
__int128 dp[100010];
pair <long long,long long> calc(__int128 add){
LineContainer lc;
dp[0]=0;
lc.addline(C*-2*v[1].first,C*(v[1].first-1)*(v[1].first-1)+C*add+1);
for (int i=1; i<=n; i++){
dp[i]=lc.query(v[i].second)+C*v[i].second*(v[i].second+2);
if (i<n){
__int128 tp=max((__int128)0,v[i].second-v[i+1].first+1);
lc.addline(C*-2*v[i+1].first,dp[i]-C*tp*tp+C*(v[i+1].first-1)*(v[i+1].first-1)+C*add+1);
}
}
return {dp[n]/C-(dp[n]%C)*add,dp[n]%C};
}
long long take_photos(int N,int m,int k,vector <int> r,vector <int> c){
int til[m];
for (int i=0; i<m; i++) til[i]=i-1;
for (int i=0; i<N; i++){
int rr=r[i],cc=c[i];
if (rr>cc) swap(rr,cc);
til[rr]=max(til[rr],cc);
}
int mx=-1;
for (int i=0; i<m; i++){
if (til[i]>mx&&i<=til[i]){
v.push_back({i,til[i]});
mx=til[i];
}
}
n=v.size();
v.insert(v.begin(),{0,0});
long long L=0,R=1e12;
while (L<R){
int mid=(L+R)/2;
if (calc(mid).second>k) L=mid+1;
else R=mid;
}
pair <long long,long long> cur=calc(L);
if (cur.second==k) return cur.first;
pair <long long,long long> nxt=calc(L+1);
if (nxt.second==cur.second) return cur.first;
return cur.first+(k-cur.second)*(nxt.first-cur.first)/(nxt.second-cur.second);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
600 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
504 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
436 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 1 |
4 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 5 |
5 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 41 |
6 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 71923 |
7 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
2 ms |
352 KB |
Wrong answer: output = 741, expected = 764 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
600 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
504 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
436 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
352 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
600 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
504 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
436 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
352 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
600 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
504 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
436 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
352 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
600 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
504 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
436 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
352 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
352 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
352 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |