oj.uz

Submission #264637

# Submission time Handle Problem Language Result Execution time Memory
264637 2020-08-14T08:08:49 Z 문홍윤(#5092) Tram (CEOI13_tram) C++17
45 / 100
 1000 ms 4368 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const LL INF=8e18;
const int INF2=1e9;

int n, q, re, rv[150010];
bool ch[150010][3];
LL dis[150010][3];
pii ans[150010];

void make_dis(){
    int d[2]={0, 0};
    for(int i=1; i<=n; i++){
        dis[i][0]=dis[i][1]=INF;
        if(ch[i][0])d[0]=i;
        if(ch[i][1])d[1]=i;
        if(d[1]){
            dis[i][0]=min(dis[i][0], 1ll+(LL)(i-d[1])*(i-d[1]));
            dis[i][1]=min(dis[i][1], (LL)(i-d[1])*(i-d[1]));
        }
        if(d[0]){
            dis[i][0]=min(dis[i][0], (LL)(i-d[0])*(i-d[0]));
            dis[i][1]=min(dis[i][1], 1ll+(LL)(i-d[0])*(i-d[0]));
        }
    }
    d[0]=d[1]=0;
    for(int i=n; i>=1; i--){
        if(ch[i][0])d[0]=i;
        if(ch[i][1])d[1]=i;
        if(d[1]){
            dis[i][0]=min(dis[i][0], 1ll+(LL)(i-d[1])*(i-d[1]));
            dis[i][1]=min(dis[i][1], (LL)(i-d[1])*(i-d[1]));
        }
        if(d[0]){
            dis[i][0]=min(dis[i][0], (LL)(i-d[0])*(i-d[0]));
            dis[i][1]=min(dis[i][1], 1ll+(LL)(i-d[0])*(i-d[0]));
        }
    }
}

pii find_dis(){
    LL maxx=0;
    pii ret=mp(INF2, INF2);
    for(int i=1; i<=n; i++){
        for(int j=0; j<2; j++){
            if(maxx<dis[i][j]){
                maxx=dis[i][j];
                ret=mp(i, j);
            }
        }
    }
    return ret;
}

void in(){
    ans[re]=find_dis();
    ch[ans[re].F][ans[re].S]=true;
    make_dis();
}

void out(int num){
    num=rv[num];
    ch[ans[num].F][ans[num].S]=false;
    make_dis();
}

int main(){
    scanf("%d %d", &n, &q);
    make_dis();
    for(int i=1; i<=q; i++){
        char c;
        scanf(" %c", &c);
        if(c=='E'){
            rv[i]=++re;
            in();
        }
        else{
            int a;
            scanf("%d", &a);
            out(a);
        }
    }
    for(int i=1; i<=re; i++)printf("%d %d\n", ans[i].F, ans[i].S+1);
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
tram.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 23 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 26 ms 364 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 4368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 4332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 1060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 4348 KB Time limit exceeded
2 Halted 0 ms 0 KB -