Submission #349696

#	Time	Username	Problem	Language	Result	Execution time	Memory
349696		daniel920712	Jousting tournament (IOI12_tournament)	C++14	100 / 100	255 ms	66924 KiB

tournament

#include <stdio.h>
#include <time.h>
#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <vector>
#include <utility>
using namespace std;
int all[1000005];
int xx=0;
struct A
{
    int l,r;
    int nxl,nxr;
    int con;
    pair < int , int > how;
    pair < long long , long long > ans;
    long long add;
    int big;
}Node[1000005];
int now=1;
int LL[1000005];
int RR[1000005];
void UPD(int here)
{
    Node[Node[here].nxl].add+=Node[here].add;
    Node[Node[here].nxr].add+=Node[here].add;
    Node[Node[here].nxl].ans.first+=Node[here].add;
    Node[Node[here].nxr].ans.first+=Node[here].add;
    Node[here].add=0;
}
pair < long long , long long > operator +(pair < long long , long long > a,pair < long long , long long > b)
{
    if(a.first>b.first) return a;
    if(a.first<b.first) return b;
    return make_pair(a.first,min(a.second,b.second));
}

void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].con=(r-l+1);
    Node[here].how=make_pair(l,r);
    Node[here].ans=make_pair((long long) 0,(long long) l);
    if(l==r)
    {
        Node[here].big=all[l];
        return;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
}
pair < int , pair < int , int > > Find(int here,int con)
{
    if(Node[here].l==Node[here].r) return make_pair(Node[here].l,Node[here].how);
    if(con<=Node[Node[here].nxl].con) return Find(Node[here].nxl,con);
    else return Find(Node[here].nxr,con-Node[Node[here].nxl].con);
}

int Find2(int l,int r,int here)
{
    if(l==Node[here].l&&r==Node[here].r) return Node[here].big;
    if(r<=(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxr);
    else return max(Find2(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find2((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
void cha(int where,int here)
{
    Node[here].con--;
    if(Node[here].l==Node[here].r) return;
    if(where<=(Node[here].l+Node[here].r)/2) cha(where,Node[here].nxl);
    else cha(where,Node[here].nxr);
}

void cha2(int l,int r,long long con,int here)
{
    xx++;
    if(Node[here].l==l&&Node[here].r==r)
    {
        //printf("%d %d\n",l,r);
        Node[here].add+=con;
        Node[here].ans.first+=con;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxr);
    else
    {
        cha2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha2((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
void cha3(int where,pair < int , int > con,int here)
{
    if(Node[here].l==where&&Node[here].r==where)
    {
        Node[here].how=con;
        return;
    }
    if(where<=(Node[here].l+Node[here].r)/2) cha3(where,con,Node[here].nxl);
    else cha3(where,con,Node[here].nxr);

}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    int who,i,j,k,tt,big,how=0;
    long long ans=0,where=0;
    for(i=0;i<N-1;i++) all[i]=K[i];
    build(0,N,0);
    for(i=0;i<C;i++)
    {
        LL[i]=Find(0,S[i]+1).second.first;
        RR[i]=Find(0,E[i]+1).second.second;
        for(j=S[i];j<E[i];j++) cha(Find(0,S[i]+1).first,0);
        cha3(Find(0,S[i]+1).first,make_pair(LL[i],RR[i]),0);
        //if(i%1000==0) printf("%d\n",i);
        //printf("%d\n",i);
    }
    //printf("aa\n");
    for(i=0;i<C;i++)
    {
        xx=0;
        if(Find2(LL[i],RR[i]-1,0)>=R) cha2(LL[i],RR[i],-1e9,0);
        cha2(LL[i],RR[i],1,0);
        //assert(xx<=50);
        //if(xx>150) printf("%d %d %d\n",LL[i],RR[i],xx);
        if(Node[0].ans.first>ans)
        {
            ans=Node[0].ans.first;
            where=Node[0].ans.second;
        }
        else if(Node[0].ans.first==ans) where=min(where,Node[0].ans.second);
        //printf("%d\n",i);
        //if(i%1000==0) printf("aaaaaaaaa %d\n",i);
    }
    return (int) where;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:112:9: warning: unused variable 'who' [-Wunused-variable]
  112 |     int who,i,j,k,tt,big,how=0;
      |         ^~~
tournament.cpp:112:17: warning: unused variable 'k' [-Wunused-variable]
  112 |     int who,i,j,k,tt,big,how=0;
      |                 ^
tournament.cpp:112:19: warning: unused variable 'tt' [-Wunused-variable]
  112 |     int who,i,j,k,tt,big,how=0;
      |                   ^~
tournament.cpp:112:22: warning: unused variable 'big' [-Wunused-variable]
  112 |     int who,i,j,k,tt,big,how=0;
      |                      ^~~
tournament.cpp:112:26: warning: unused variable 'how' [-Wunused-variable]
  112 |     int who,i,j,k,tt,big,how=0;
      |                          ^~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51