Submission #392642

#	Time	Username	Problem	Language	Result	Execution time	Memory
392642		Antekb	Robots (IOI13_robots)	C++14	90 / 100	3075 ms	9428 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=(1<<16);
long long M[2*N], lazy[2*N];
void init(){
	for(int i=0; i<2*N; i++){
		M[i]=0;
		lazy[i]=0;
	}
}
void prop(int v){
	if(v>=N || !lazy[v])return;
	int l=2*v, r=2*v+1;
	lazy[l]+=lazy[v];
	lazy[r]+=lazy[v];
	M[l]+=lazy[v];
	M[r]+=lazy[v];
	lazy[v]=0;
}
void add(int v, int L, int R, int l, int r, int c){
	if(l==L && r==R){
		lazy[v]+=c;
		M[v]+=c;
		return;
	}
	int m=(L+R)>>1;
	prop(v);
	if(l<=m)add(2*v, L, m, l, min(r, m), c);
	if(r>m)add(2*v+1, m+1, R, max(m+1, l), r, c);
	M[v]=min(M[2*v], M[2*v+1]);
	return;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    pair<int, int> tab[T];
    for(int i=0; i<T; i++){
    	tab[i]={upper_bound(X, X+A, W[i])-X, upper_bound(Y, Y+B, S[i])-Y};
    	if(tab[i].st==A && tab[i].nd==B)return -1;
    	//cout<<tab[i].st<<" "<<tab[i].nd<<"\n";
    }
    sort(tab, tab+T);
    reverse(tab, tab+T);
    long long ans=0;
    int pref[2][B+1];
    for(int i=0; i<=B; i++)pref[0][i]=pref[1][i]=0;
    int wsk=0;
    for(int i=A; i>=0; i--){
        int sum=0;
        for(int j=B; j>=0; j--){
            while(wsk<T && tab[wsk].st==i && tab[wsk].nd==j)sum++, wsk++;
            pref[i&1][j]=pref[!(i&1)][j]+sum;
            while(ans*(A+B-i-j)<pref[i&1][j])ans++;
        }
    }
    return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10