| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 36013 |
2017-12-04T08:25:12 Z |
YoLo |
Pinball (JOI14_pinball) |
C++14 |
|
9 ms |
14680 KB |
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
#define N 1000000
#define lmax LONG_LONG_MAX
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
int n, m, lef[100009], rig[100009], a[100009], b[100009], c[100009], d[100009], f[100009], itl[400009], itr[400009], p[100009], ans = lmax;
void updl(int k, int l, int r, int pos, int val)
{
if(r < pos || l > pos || r < l)
return;
if(r == pos && l == pos)
{
itl[k] = val;
return;
}
int mid = (l + r) / 2;
updl(k * 2, l, mid, pos, val);
updl(k * 2 + 1, mid + 1, r, pos, val);
itl[k] = min(itl[k * 2], itl[k * 2 + 1]);
}
int getl(int k, int l, int r, int L, int R)
{
if(r < L || R < l || r < l)
return 1e18;
if(L <= l && r <= R)
return itl[k];
int mid = (l + r) / 2;
return min(getl(k * 2, l, mid, L, R), getl(k * 2 + 1, mid + 1, r, L, R));
}
void updr(int k, int l, int r, int pos, int val)
{
if(r < pos || l > pos || r < l)
return;
if(r == pos && l == pos)
{
itr[k] = val;
return;
}
int mid = (l + r) / 2;
updr(k * 2, l, mid, pos, val);
updr(k * 2 + 1, mid + 1, r, pos, val);
itr[k] = min(itr[k * 2], itr[k * 2 + 1]);
}
int getr(int k, int l, int r, int L, int R)
{
if(r < L || R < l || r < l)
return 1e18;
if(L <= l && r <= R)
return itr[k];
int mid = (l + r) / 2;
return min(getr(k * 2, l, mid, L, R), getr(k * 2 + 1, mid + 1, r, L, R));
}
bool cmp(int u, int v)
{
return c[u] < c[v];
}
signed main()
{
ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> a[i] >> b[i] >> c[i] >> d[i], f[i] = i;
sort(f + 1, f + 1 + n, cmp);
for(int i = 1; i <= n; i ++)
p[f[i]] = i;
for(int i = 1; i <= 400000; i ++)
itl[i] = itr[i] = 1e18;
for(int i = 1; i <= n; i ++)
{
int l = 1;
int r = n;
while(l < r)
{
int mid = (l + r) / 2;
if(c[f[mid]] < a[i])
l = mid + 1;
else
r = mid;
}
int ll = l;
l = 1;
r = n;
while(l < r)
{
int mid = (l + r + 1) / 2;
if(c[f[mid]] > b[i])
r = mid - 1;
else
l = mid;
}
int rr = l;
if(a[i] == 1)
lef[i] = d[i];
else
{
int tak = getl(1, 1, n, ll, rr);
if(tak < 1e18)
lef[i] = tak + d[i];
}
if(lef[i] > 0)
updl(1, 1, n, p[i], lef[i]);
if(b[i] == m)
rig[i] = d[i];
else
{
int tak = getr(1, 1, n, ll, rr);
if(tak < 1e18)
rig[i] = tak + d[i];
}
if(rig[i] > 0)
updr(1, 1, n, p[i], rig[i]);
if(rig[i] > 0 && lef[i] > 0)
ans = min(ans, rig[i] + lef[i] - d[i]);
cout << i << ' ' << l << ' ' << r << ' ' << p[i] << ' ' << lef[i] << ' ' << rig[i] << endl;
}
if(ans < 1e16)
cout << ans;
else
cout << -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
14680 KB |
Execution killed because of forbidden syscall writev (20) |
| 2 |
Halted |
0 ms |
0 KB |
- |
