Comment deleted

I solved it using handmade linked lists. Use arrays values, last, prev. All numbers are stored in array values, one after another. last[s] is the index of the last value of the s-th stack (and values[last[s]] is the value itself). And prev[i] is the index of the element before element with index i (their values are values[prev[i]] and values[i] correspondingly).

It requires one small array (last, of length about 1000) and two big arrays (values, prev, of length about 100000). So the memory usage will be 100000 * 4 * 2 = 0.8 MB, and it doesn't fit. But all elements of array prev have values no more than 2^17. So we can consider that the first 17 bits of the array prev store prev[0], the second 17 bits store prev[1] and so on — about 0.2 MB instead of 0.4. It passes.

My solution takes 0.171s and 540 KB and is as follows:

1. We know that there are at most 100,000 operations and it's guaranteed that all operations will be valid. In the worst case the operations would be PUSH A B, where A is the same for all operations. In the average case the sum of elements in all stacks will be at most 100,000, so we only need a container of 100,000 elements, lets call it S.

2. Now the problem is to find the initial position of each stack A in S, let top[i] be the top position of stack i. I have processed all the instructions to find the maximum height of each stack and then:

    prev = 0

    // Repeat for all stacks
    top[maxi()] = prev
    prev = maxh() + 1

where maxi() is the index of the tallest stack and maxh() is the height of that tallest stack, drop the last stack of the rest and repeat the steps for all stacks(1000). maxi() and maxh() are only theoretical functions but I have used an array pos[1000][2] to store the index->max_heigth and, then I have sorted in non increasing order.

To process all the instructions, would be necessary to store all the instructions, and then use it in the simulation and later in the real task, however, we have little memory, and since in the worst case we'll need to store 200,000(~800kb) elements this isn't an option. My solution was to read all the input and then rewind the stdin and read the input again to do the real task.

PUSH:

    S[top[A]++] = B;

POP:

    print S[--top[A]];

Try this and if after this you need the code I'll post it here too.

EDIT: The code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Position { int index, maxx; };
const int LIMIT = 1000;
int S[105000];
int top[LIMIT + 1];
Position P[LIMIT + 1];

bool cmp(const Position &a, const Position &b) { return a.maxx > b.maxx; }

int main(int argc, char **argv)
{
  int n, i, a, b, prev = 0;
  char command[10];
  scanf("%d", &n);

  for (i = 0; i < LIMIT; i++) {
    P[i].index = i;
    P[i].maxx = 0;
  }

  for (i = 0; i < n; i++) {
    scanf("%s", command);
    if (command[1] == 'U') {
      scanf("%d %d", &a, &b);
      a--;

      S[a]++;
      P[a].maxx = max(P[a].maxx, S[a]);
    } else {
      scanf("%d", &a);
      S[a-1]--;
    }
  }

  sort(P, P + LIMIT, cmp);

  for (i = 0; i < LIMIT; i++) {
    top[P[i].index] = prev;
    prev += P[i].maxx + 2;
  }

  rewind(stdin);

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s", command);
    
    if (command[1] == 'U') {
      scanf("%d %d", &a, &b);
      a--;
      S[top[a]++] = b;
    } else {
      scanf("%d", &a);
      printf("%d\n", S[--top[a-1]]);
    }
  }

  return 0;
}

I have tried some optimization to reduce memory but the saving is only 14 KB.

#include <stdio.h>
#include <stdlib.h>
#define max(a,b) (((a) > (b)) ? (a) : (b))

unsigned int LIMIT = 1000;
unsigned int S[100010];
unsigned int top[1001];
unsigned int P[1001]; // First 20 bits for the height and last 12 for index
unsigned int amax, bmax;
unsigned int mb = (1 << 20) - 1;
unsigned int ib = ~((1 << 20) - 1);

int cmp(const void *a, const void *b)
{
  amax = (*(int *)a) & mb;
  bmax = (*(int *)b) & mb;
  return amax - bmax;
}

int main(int argc, char **argv)
{
  unsigned int n, i, a, b, prev = 0, maxx;
  char command[5];
  scanf("%d", &n);

  for (i = 0; i < LIMIT; i++)
    P[i] = i << 20;

  for (i = 0; i < n; i++) {
    scanf("%s", command);
    if (command[1] == 'U') {
      scanf("%d %d", &a, &b);
      a--;

      S[a]++;
      maxx = P[a] & mb;
      maxx = max(maxx, S[a]);
      P[a] = maxx | (P[a] & ib);
    } else {
      scanf("%d", &a);
      S[a-1]--;
    }
  }

  qsort(P, LIMIT, sizeof(int), cmp);

  for (i = 0; i < LIMIT; i++) {
    top[P[i] >> 20] = prev;
    prev += (P[i] & mb);
  }

  rewind(stdin);

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s", command);

    if (command[1] == 'U') {
      scanf("%d %d", &a, &b);
      a--;
      S[top[a]++] = b;
    } else {
      scanf("%d", &a);
      printf("%d\n", S[--top[a-1]]);
    }
  }

  return 0;
}