Submission #1032816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032816		Dan4Life	Teams (IOI15_teams)	C++17	34 / 100	4040 ms	524288 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
const int mxN = (int)5e5+10;
const int mxM = (int)2e5+10;
ar2 v[mxN]; int n;
multiset<int> S;
const int B = sqrt(mxM);
const int mxLg = __lg(mxN)+1;
const int mxSeg = mxN*4*mxLg;
int a[mxN], b[mxN];
int seg[mxSeg], L[mxSeg], R[mxSeg], root[mxSeg];
int segNodes = 1;

struct Fenwick2D{
	unordered_map<int,int> fen[mxN];
    void init(int n, int m){
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                fen[i][j]=0;
    }
    void upd(int _x, int _y, int v){
        _x++, _y++;
        for(int x = _x; x<mxN; x+=x&-x)
            for(int y = _y; y < mxN; y+=y&-y)
                fen[x][y]+=v;
    }
    int sum(int _x, int _y){
        int s = 0; _x++, _y++;
        for(int x = _x; x>0; x-=x&-x)
            for(int y = _y; y>0; y-=y&-y)
                s+=fen[x][y];
        return s;
    }
    int sum(int x1, int y1, int x2, int y2){
        return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);
    }
} fen2d;

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++) a[i]=A[i],b[i]=B[i];
	for(int i = 0; i < n; i++) v[i]={a[i],b[i]},fen2d.upd(a[i],b[i],1);
    sort(v,v+n,[&](ar2 x, ar2 y){ return x[1]>y[1]; }); 
}

int dp[B+10];
int f(int j, int i, int a[]){
	return dp[j]+fen2d.sum(a[j]+1,a[i],a[i],n);
}

int can(int m, int a[]) {
	sort(a,a+m); 
	if(m>=B){
		reverse(a,a+m);
		int j = 0; S.clear();
		for(int i = 0; i < m; i++){
			int x = a[i];
			while(j<n and v[j][1]>=a[i]) 
				S.insert(v[j][0]), j++;
			while(x--){
				auto itr = S.upper_bound(a[i]);
				if(itr==begin(S)) return 0;
				S.erase(--itr);
			}
		}
		return 1;
	}
	deque<int> dq; dq.clear();
	for(int i = 0; i < m; i++){
		dp[i] = fen2d.sum(1,a[i],a[i],n);
		while(sz(dq)>1 and f(end(dp)[-2],i,a) < f(end(dp)[-1],i,a)) dq.pop_back();
		
		if(sz(dq)){
			//int j = dq.back();
			for(auto j : dq) dp[i] = min(dp[i], f(j,i,a));
		}
		dp[i]-=a[i];
		if(dp[i]<0) return 0;
		dq.pb(i);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp:11:19: warning: conversion from 'double' to 'int' changes value from '4.4722477570009471e+2' to '447' [-Wfloat-conversion]
   11 | const int B = sqrt(mxM);
      |               ~~~~^~~~~
teams.cpp: In member function 'void Fenwick2D::init(int, int)':
teams.cpp:20:19: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   20 |     void init(int n, int m){
      |               ~~~~^
teams.cpp:9:17: note: shadowed declaration is here
    9 | ar2 v[mxN]; int n;
      |                 ^
teams.cpp: In member function 'void Fenwick2D::upd(int, int, int)':
teams.cpp:25:34: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   25 |     void upd(int _x, int _y, int v){
      |                              ~~~~^
teams.cpp:9:5: note: shadowed declaration is here
    9 | ar2 v[mxN]; int n;
      |     ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:43:31: warning: declaration of 'B' shadows a global declaration [-Wshadow]
   43 | void init(int N, int A[], int B[]) {
      |                           ~~~~^~~
teams.cpp:11:11: note: shadowed declaration is here
   11 | const int B = sqrt(mxM);
      |           ^
teams.cpp: In function 'int f(int, int, int*)':
teams.cpp:51:25: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   51 | int f(int j, int i, int a[]){
      |                     ~~~~^~~
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:55:20: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   55 | int can(int m, int a[]) {
      |                ~~~~^~~
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23