제출 #671014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671014		alvingogo	Teams (IOI15_teams)	C++14	0 / 100	992 ms	232828 KiB

teams

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
	struct no{
		int lch=-1,rch=-1,val=0;
	};
	vector<no> st;
	int newe(no x){
		st.push_back(x);
		return st.size()-1;
	}
	void pull(int x){
		st[x].val=st[st[x].lch].val+st[st[x].rch].val;
	}
	int build(int L,int R){
		if(L==R){
			int x=newe({-1,-1,0});
			return x;
		}
		int m=(L+R)/2;
		int a=build(L,m);
		int b=build(m+1,R);
		int x=newe({a,b,0});
		return x;
	}
	int update(int v,int L,int R,int p){
		if(L==R){
			int x=newe(st[v]);
			st[x].val++;
			return x;
		}
		int m=(L+R)/2;
		if(p<=m){
			int a=update(st[v].lch,L,m,p);
			int x=newe(st[v]);
			st[x].lch=a;
			pull(x);
			return x;
		}
		else{
			int b=update(st[v].rch,m+1,R,p);
			int x=newe(st[v]);
			st[x].rch=b;
			pull(x);
			return x;
		}
	}
	int query(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].val;
		}
		int m=(L+R)/2;
		if(r<=m){
			return query(st[v].lch,L,m,l,r);
		}
		else if(l>m){
			return query(st[v].rch,m+1,R,l,r);
		}
		else{
			return query(st[v].lch,L,m,l,m)+query(st[v].rch,m+1,R,m+1,r);
		}
	}
	int bs(int v1,int v2,int L,int R,int k){
		if(L==R){
			return L;
		}
		int s=st[st[v2].lch].val-st[st[v1].lch].val;
		int m=(L+R)/2;
		if(s>=k){
			return bs(st[v1].lch,st[v2].lch,L,m,k);
		}
		else{
			return bs(st[v1].rch,st[v2].rch,m+1,R,k-s);
		}
	}
}st;

int n;
vector<int> rt;
int get(int l,int r,int u,int d){
	//cout << l << " " << r << " " << u << " " << d << "\n";
	return st.query(rt[r],0,n,u,d)-(l==0?0:st.query(rt[l-1],0,n,u,d));
}

vector<int> lis;
void init(int N,int a[],int b[]){
	n=N;
	lis.clear();
	vector<pair<int,int> > c;
	for(int i=0;i<n;i++){
		c.push_back({b[i],a[i]});
	}
	sort(c.begin(),c.end());
	lis.push_back(0);
	for(int i=0;i<n;i++){
		lis.push_back(c[i].fs);
		c[i].fs=i;
	}
	vector<vector<int> > d(n+1);
	for(int i=0;i<n;i++){
		d[c[i].sc].push_back(c[i].fs);
	}
	rt.resize(n+1);
	rt[0]=st.build(0,n);
	for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(auto h:d[i]){
			rt[i]=st.update(rt[i],0,n,h);
		}
	}
	//done :happy_mention:
}
struct DQ{
	int id,mx,sum;
};
int can(int m,int k[]){
	sort(k,k+m);
	vector<DQ> v;
	v.push_back({0,n,0});
	for(int i=0;i<m;i++){
		int a=k[i];
		int nw=0;
		int nxt=0;
		int ut=upper_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
		int lt=lower_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
		while(v.size()){
			auto h=v.back();
			if(h.mx<lt){
				h.mx=lt;
				h.sum=get(h.id+1,a,0,lt);
			}
			int zz=get(h.id+1,a,0,h.mx)-h.sum;
			//cout << zz << "\n";
			if(zz<k[i]){
				k[i]-=zz;
				nw+=h.sum;
				v.pop_back();
			}
			else{
				h.sum+=nw+a;
				nxt=st.bs(rt[h.id+1],rt[a],0,n,h.sum);
				k[i]=0;
				v.back()=h;
				break;
			}
		}
		if(k[i]){
			return 0;
		}
		v.push_back({a,nxt,0});
	}
	return 1;
}





/*

#include <stdio.h>
#include <stdlib.h>

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

int main() {
	AquA;
    int N;
    cin >> N;
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) {
    	cin >> A[i];
		cin >> B[i];
    }
    init(N, A, B);
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
    	int M;
    	cin >> M;
		int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		cin >> K[j];
    	}
    	cout << can(M,K) << "\n";
    }
    return 0;
}

*/

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

teams.cpp: In member function 'int ST::newe(ST::no)':
teams.cpp:16:19: warning: conversion from 'std::vector<ST::no>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |   return st.size()-1;
      |          ~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:130:58: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  130 |   int ut=upper_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:131:58: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  131 |   int lt=lower_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:130:7: warning: unused variable 'ut' [-Wunused-variable]
  130 |   int ut=upper_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
      |       ^~

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