Submission #16884407

---

Source Code Expand

// {{{ Boilerplate Code <--------------------------------------------------
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define ALL(A)     (A).begin(), (A).end()

using namespace std;

// }}}

int main(){
        long long N,Q;
        cin>>N>>Q;

        int sqn=sqrt(N);

        long long rev=0;

        int len[2][200000];
        int lensq[2][1000];

        FOR(i,0,N){
                len[0][i]=N-2;
                len[1][i]=N-2;
        }

        FOR(i,0,N){
                lensq[0][i]=N-2;
                lensq[1][i]=N-2;
        }

        FOR(i,0,Q){
                int dir,x;
                cin>>dir>>x;
                --dir;

                int opdir=1-dir;
                int sqx=x/sqn;

                int now=min(len[dir][x],lensq[dir][sqx]);

                rev+=now;

                now+=2;
                FOR(j,0,now/sqn){
                        lensq[opdir][j]=min(lensq[opdir][j],x-2);
                }
                FOR(j,(now/sqn)*sqn,now){
                        len[opdir][j]=min(len[opdir][j],x-2);
                }

        }


        cout<<(N-2)*(N-2)-rev<<endl;
}

Submission Info

Judge Result