제출 #747091

#제출 시각아이디문제언어결과실행 시간메모리
747091Username4132팀들 (IOI15_teams)C++14
34 / 100
4059 ms370672 KiB
#include "teams.h" #include<iostream> #include<vector> #include<algorithm> using namespace std; using pii = pair<int, int>; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) #define PB push_back #define F first #define S second struct Vertex{ int sum; Vertex *l, *r; Vertex(int Sum=0) : sum(Sum), l(NULL), r(NULL){} Vertex(Vertex* le, Vertex* ri) : sum(le->sum + ri->sum), l(le), r(ri){} }; Vertex* build(int tl, int tr){ if(tl==tr) return new Vertex; int tm = (tl+tr)>>1; return new Vertex(build(tl, tm), build(tm+1, tr)); } int sum(Vertex* v, int tl, int tr, int l, int r){ if(l>r) return 0; if(l==tl && r==tr) return v->sum; int tm = (tl+tr)>>1; return sum(v->l, tl, tm, l, min(r, tm)) + sum(v->r, tm+1, tr, max(l, tm+1), r); } Vertex* modify(Vertex* v, int tl, int tr, int p, int value){ int tm = (tl+tr)>>1; if(tl==tr) return new Vertex(v->sum+value); if(p<=tm) return new Vertex(modify(v->l, tl, tm, p, value), v->r); else return new Vertex(v->l, modify(v->r, tm+1, tr, p, value)); } const int MAXN=500010, SQ=1010; int n, aa[MAXN], bb[MAXN], uniq[SQ], req[SQ], arr[SQ][SQ]; pii stu[MAXN]; Vertex* roots[MAXN]; void init(int N, int A[], int B[]) { n=N; forn(i, n) stu[i].F=aa[i]=A[i], stu[i].S=bb[i]=B[i]; sort(stu, stu+n); sort(aa, aa+n); sort(bb, bb+n); roots[0]=build(0, n-1); forn(i, n){ int posB=lower_bound(bb, bb+n, stu[i].S)-bb; roots[i+1]=modify(roots[i], 0, n-1, posB, 1); } } int count(int tx, int ty){ int x = upper_bound(aa, aa+n, tx) - aa; int y = upper_bound(bb, bb+n, ty) - bb; if(y==0) return 0; return sum(roots[x], 0, n-1, 0, y-1); } int count(int tx1, int tx2, int ty1, int ty2){ return count(tx1, ty1) + count(tx2, ty2) - count(tx1, ty2) - count(tx2, ty1); } int can(int m, int K[]) { int suu=0, sz=0; forn(i, m){ suu+=K[i]; if(suu>n) return 0; } sort(K, K+m); forn(i, m){ if(i==0 || K[i]!=K[i-1]) uniq[sz]=K[i], req[sz]=1, ++sz; else req[sz-1]++; } forn(i, sz) req[i]*=uniq[i]; forn(i, sz) forsn(j, i, sz) arr[i][j]=0; forn(i, sz) forsn(j, i, sz){ int tx1 = (i? uniq[i-1] : 0), tx2=uniq[i]; int ty1 = uniq[j]-1, ty2 = (j==sz-1? MAXN : uniq[j+1]-1); arr[i][j]=count(tx1, tx2, ty1, ty2); } forn(i, sz){ forsn(j, i, sz){ if(req[i]>arr[i][j]) req[i]-=arr[i][j], arr[i][j]=0; else{ arr[i][j]-=req[i]; req[i]=0; break; } } if(req[i]>0) return 0; forsn(j, i+1, sz) arr[i+1][j]+=arr[i][j]; } return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:55:43: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   55 |   int posB=lower_bound(bb, bb+n, stu[i].S)-bb;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int count(int, int)':
teams.cpp:61:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   61 |  int x = upper_bound(aa, aa+n, tx) - aa;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
teams.cpp:62:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   62 |  int y = upper_bound(bb, bb+n, ty) - bb;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...