oj.uz

Submission #79806

# Submission time Handle Problem Language Result Execution time Memory
79806 2018-10-16T13:51:04 Z AngelKnows Pinball (JOI14_pinball) C++14
0 / 100
 3 ms 1340 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=100000+10;
const double eps=1e-5;
const int mo=1e9+7;

int m,n;
struct node {
	int l,r,m,w;
} b[N];
int tot;
struct data {
	int val;
	int id;
	int t;
} a[3*N];
int cnt;
int seg[12*N];
int ld[N],rd[N];
void build(int k,int l,int r) {
	if (l==r) {
		seg[k]=inf;
		return;
	}
	seg[k]=inf;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int x,int v) {
	if (l==r) {
		seg[k]=min(seg[k],v);
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) update(k<<1,l,mid,x,v);
	else update(k<<1|1,mid+1,r,x,v);
	seg[k]=min(seg[k<<1],seg[k<<1|1]);
}
int query(int k,int L,int R,int l,int r) {
	if (L==l&&R==r) {
		return seg[k];
	}
	int mid=(L+R)>>1;
	if (r<=mid) {
		return query(k<<1,L,mid,l,r);
	} else if (l>mid) {
		return query(k<<1|1,mid+1,R,l,r);
	} else {
		return min(query(k<<1,L,mid,l,mid),query(k<<1|1,mid+1,R,mid+1,r));
	}
}
bool cmp(data x,data y) {
	return x.val<y.val;
} 
int main() {
 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d %d",&m,&n);
    FOR(i,m) {
    	scanf("%d %d %d %d",&b[i].l,&b[i].r,&b[i].m,&b[i].w);
    	a[++tot]=data{b[i].l,i,1};
		a[++tot]=data{b[i].m,i,2};
		a[++tot]=data{b[i].r,i,3};	
	}
	sort(a+1,a+1+tot,cmp);
	FOR(i,tot) {
		if (i==1||a[i].val!=a[i-1].val) {
			++cnt;
		}
		int id=a[i].id;
		int t=a[i].t;
		if (t==1) {
			b[id].l=cnt;
		} else if (t==2) {
			b[id].m=cnt;
		} else {
			b[id].r=cnt;
		}
	}
	memset(ld,0x3f,sizeof ld);
	memset(rd,0x3f,sizeof rd);
	build(1,1,cnt);
	FOR(i,m) {
		int l=b[i].l,r=b[i].r;
		int t=query(1,1,cnt,l,r);
		if (t!=inf) {
			update(1,1,cnt,b[i].m,t+b[i].w);
		}
		if (b[i].l==1) {
			update(1,1,cnt,b[i].m,b[i].w);
		}
	}
	FOR(i,m) ld[i]=query(1,1,cnt,b[i].m,b[i].m);
	build(1,1,cnt);
	FOR(i,m) {
		int l=b[i].l,r=b[i].r;
		int t=query(1,1,cnt,l,r);
		if (t!=inf) {
			update(1,1,cnt,b[i].m,t+b[i].w);
		}
		if (b[i].r==cnt) {
			update(1,1,cnt,b[i].m,b[i].w);
		}
	}
	FOR(i,m) rd[i]=query(1,1,cnt,b[i].m,b[i].m);
	int ans=inf;
	FOR(i,m) if (ld[i]!=inf&&rd[i]!=inf) {
		ans=min(ans,ld[i]+rd[i]-b[i].w);
	}
	if (ans!=inf) cout<<ans<<endl;
	else cout<<-1<<endl;
	return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m,&n);
     ~~~~~^~~~~~~~~~~~~~~
pinball.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d %d %d",&b[i].l,&b[i].r,&b[i].m,&b[i].w);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1192 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 3 ms 1340 KB Output is correct
5 Incorrect 3 ms 1340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1192 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 3 ms 1340 KB Output is correct
5 Incorrect 3 ms 1340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1192 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 3 ms 1340 KB Output is correct
5 Incorrect 3 ms 1340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1192 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 3 ms 1340 KB Output is correct
5 Incorrect 3 ms 1340 KB Output isn't correct
6 Halted 0 ms 0 KB -